[프로그래머스 : 레벨3] 입국심사 : 이분탐색(Java)

이번 문제는 사실 문제를 보고 어떻게 풀어야 할지 감이 전혀 안잡혔다.

사실 안잡힌건 아니고 감은 잡혔지만 내가 생각한 방식으로 문제를 풀었다간 시간복잡도고 O(n)으로 나와서

제한사항에 나와 있는 엄청난 데이터를 상대로 하기엔 런아웃 에러가 날게 뻔했다.

그래서 어떻게 풀어야 할지 몰라 답지를 봤다.

 

일단 문제부터 살펴보자.

 

문제 설명

 

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

 

입출력 예 설명

 

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

 

문제 풀이

 

이번 문제에서는 특정 시간안에 두명의 심사관이 n명을 심사할수 있는 최소의 시간을 탐색하는게 주된 목적이다.

따라서 우리가 탐색해야할것은 n명을 심사하는데 필요한 최소시간이다.

 

그럼 우리가 제일 먼저 해야할것은 start 값과 end 값을 지정하는것이다.

다른사람들의 풀이를 보면 start 값은 0으로 설정을 하고 end 값은 해당 자료형의 최대값으로 설정 하였다.

        long start, mid, end;
        start = 0;
        end = Long.MAX_VALUE;

그리고 이제 심사시간의 최소시간을 찾기 위해 이분탐색의 기본인

start가 end보다 크거나 같아질때까지 반복해서 반씩 쪼개는것을 해서 최소시간을 찾으면 된다.

 while(start <= end){

 }

이제 위의 while 문안에서 우리가 해야할것은

start와 end의 중간 값 mid를 구하고  

mid를 time[]에 있는 심사관의 심사시간으로 나누는것이다.

나는 왜 mid를 심사시간으로 나누지 했는데

나누는 이유가 중간값이 두명의 심사관이 n명을 심사하는데 걸리는 시간을 뜻하는것이기 때문이다.

(이진트리로 따지자면 node와 비슷한 역할을 한다고 보면 된다.)

그래서 아래와 같이 mid를 time[] 안에 있는 원소들로 나누는 반복문을 사용했다.

            mid = (start + end) / 2;
            sum = 0;
            // 주어진 시간동안 몇명 검사 할 수 있는지 누적합
            for(int i=0; i<times.length; i++){
                sum += mid / times[i]; //나눈값을 기존의 sum 값에 얺음
                
                System.out.println("심사관 "+i+" : "+sum);
                
                if(sum >= n) //만약 중간값을 time[i]으로 나눈게 크면 break
                    break;
            }

이때 sum을 구하는 이유는 두명의 심사관이 검사할수 있는 사람의 수가 검사하려는 사람의 수와 같은지 확인하기 위해

sum이라는 변수를 만들었고 time[]의 원소로 mid를 나눴을때 검사하려는 사람의 수 n보다 크면 break해

불필요한 연산을 없앴다.

 

그리고 위과정을 거치면 이제 값이 크냐 작냐에 따라 start와 end 값을 수정한다.

특정시간 mid 동안에 검사할수 있는 사람의 수 sum 이 검사하려는 사람의 수 n보다 작다면 

start = mid+1로 바꾸고

sum이 n보다 크다면 

end = mid-1 로 바꿔

검색하려는 수를 절반으로 계속해서 잘라 나간다.

그리고 answer는 중간값과 이전에 설정해둔 값중 작은 값을 채택해서 answer의 값을 넣어준다.

            if(n > sum){
                start = mid + 1;
            }
            else{ 
                end = mid - 1;
                answer = Math.min(answer, mid);
                System.out.println("answer : "+answer); 
            }

따라서 위과정을 한번살펴보면 start와 end는 

계속해서 잘라나가다가 어느순간부터 아래와 같은 결과를 보인다.

 

start : 0
end : 126
mid : 63
answer : 127
심사관 0 : 9
end : 62
answer : 63

---

start : 0
end : 62
mid : 31
answer : 63
심사관 0 : 4
심사관 1 : 7
end : 30
answer : 31

---

start : 0
end : 30
mid : 15
answer : 31
심사관 0 : 2
심사관 1 : 3
start : 16

---

start : 16
end : 30
mid : 23
answer : 31
심사관 0 : 3
심사관 1 : 5
start : 24

---

start : 24
end : 30
mid : 27
answer : 31
심사관 0 : 3
심사관 1 : 5
start : 28

---

start : 28
end : 30
mid : 29
answer : 31
심사관 0 : 4
심사관 1 : 6
end : 28
answer : 29

---

start : 28
end : 28
mid : 28
answer : 29
심사관 0 : 4
심사관 1 : 6
end : 27
answer : 28

 

 

이렇게 위와 같은 방식으로 하면 최단시간을 찾을수가 있다.

 

 

느낀점

1. 이분탐색에서 제일 중요한점은 무엇을 어디에서 탐색할것이냐다.