코딍코딍
코딩기록
코딍코딍
전체 방문자
오늘
어제
  • 분류 전체보기 (271)
    • 개발 (2)
    • Java (1)
    • 스프링 (28)
    • JPA (11)
    • Git (3)
    • 알고리즘 (160)
      • 백준 (132)
      • 프로그래머스 (8)
      • SWEA (20)
    • 토이 프로젝트 (14)
      • 간단한 Springboot CRUD (1)
      • 게시판 프로젝트 (13)
    • 알고리즘 개념정리 (8)
    • 오류 해결 (13)
    • 보류 (0)
    • AWS (5)
    • 트러블 슈팅 (0)
    • 회고 (3)
    • CS (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

최근 글

티스토리

hELLO · Designed By 정상우.
코딍코딍

코딩기록

알고리즘/프로그래머스

입국심사

2023. 6. 15. 13:11

https://school.programmers.co.kr/learn/courses/30/lessons/43238#qna

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

틀린 소스코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        TreeMap<Long, Long> map = new TreeMap<>();
        for (int time : times)
            map.put((long)time, (long)time);

        for (int i = 0; i < n - 1; i++) {
            Map.Entry<Long, Long> entry = map.firstEntry();
            Long key = entry.getKey();
            Long value = entry.getValue();
            map.remove(key);
            map.put(key + value, value);
        }

        answer = map.firstEntry().getKey();
        return answer;
    }
}

 

 

틀린 이유

TreeMap을 사용하여 문제를 해결하려 하였다. 하지만 TreeMap은 중복키를 허용하지 않기 때문에 만약 (3, new int []{1,1,1})이 입력으로 들어오는 경우 결과값은 1이 나와야 하지만 3이 나온다. 애초에 n의 수는 최대 1억이기 때문에 for문을 돌리면서 시간초과가 날 것이다.

 

 

소스코드

import java.util.*;

class Solution {
    long max = 1000000000;
    int[] time;
    int N;

    public long solution(int n, int[] times) {
        N = n;
        time = times;
        long left = 1;
        long right = max * max;
        while(left<right) {
            long mid = (left + right) / 2;
            if(possible(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
    boolean possible(long mid) {
        long n = N;
        for (int i : time) {
            n -= mid / i;
        }
        return n <= 0;
    }
}

 

 

해결방법

이진 탐색을 사용하였다. 10만*log(10억*10억) => 약 600만 이므로 시간초과가 나지 않는다.

 

'알고리즘 > 프로그래머스' 카테고리의 다른 글

네트워크  (0) 2023.06.29
게임 맵 최단거리  (0) 2023.06.16
오픈채팅방  (0) 2023.06.14
디펜스 게임  (0) 2023.06.14
뒤에 있는 큰 수 찾기  (0) 2023.04.10
    '알고리즘/프로그래머스' 카테고리의 다른 글
    • 네트워크
    • 게임 맵 최단거리
    • 오픈채팅방
    • 디펜스 게임
    코딍코딍
    코딍코딍
    ㅎ2

    티스토리툴바