입국심사

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

프로그래머스

 

 

틀린 소스코드

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만 이므로 시간초과가 나지 않는다.