프로그래머스 이분 탐색 문제 : 입국심사

문제 설명

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분에 모든 사람의 심사가 끝납니다.

내 코드...

매우 부끄럽지만 내 첫 코드는 다음과 같았다. 이분 탐색 문제는 처음이라 생소해서 대체 어떻게 이분 탐색으로 이 문제를 풀 수 있는 지 감이 오지 않았다. 그냥 생각나는 대로 답을 구할 수 있는 방법을 강구했다.

public class No43238 {
  static long solution(int n, int[] times) {
    Customer[] customers = new Customer[n];
    for (int i = 0; i < times.length; i++) {
      customers[i] = new Customer(times[i], times[i]);
    }

    for  (int i = times.length; i < n; i++) {
      long min = customers[i - 1].time + customers[i - 1].num;
      long num = 0;
      for (int j = i - 1; j >= i - times.length; j--) {
        if (min > customers[j].time + customers[j].num) {
          min = customers[j].time + customers[j].num;
          num = customers[j].num;
        }
        customers[i] = new Customer(min, num);
      }
    }
    return customers[n - 1].time;
  }

  static class Customer {
    long time = 0;
    long num = 0;

    public Customer(long time, long num) {
      this.time = time;
      this.num = num;
    } 
  }

  public static void main(String[] args) {
    System.out.println(solution(6, new int[] {7, 10}));
  }
}

알고리즘에 객체를 만들어 푼건 처음이었다....;;; 각 손님이 기다리고 심사를 받을 최소 시간을 저장하는 time과 선택할 심사대(에서 걸릴 시간)를 num으로 지정하고 이 손님들이 담긴 배열의 마지막 요소가 저장하는 time이 답이라고 설정했다.

 

그리고 각 배열의 요소들의 time과 num을 결정하는 것은 이 요소 앞에 있는 심사대 개수만큼의 요소들이었다. 각 요소들은 어떤 심사대든 간에 하나씩 차지하였을 것이고, 누구 뒤에 서는 것이 이득인지를 비교하여 제일 짧은 시간이 걸리는 심사대를 선택할 것이라 생각했다. 지금생각해보면 여기서 제시된 케이스에는 정상적으로 결과를 도출하지만 심사대가 여러개로 늘어났을 경우 혹은 더 복잡해지는 경우에, 의미가 없어지는 알고리즘이라고 생각한다.

 

깨끗이 포기하고, 남의 코드를 참고했다.

 

다른 코드

import java.util.Arrays;

class No43238_ans {
  public long solution(int n, int[] times) {
    Arrays.sort(times);
    long min = 1;
    long max = (long)times[times.length - 1] * n;
    long mid = 0;
    long sum;
    long answer = max;

    while (min <= max) {
      sum = 0;
      mid = (min + max) / 2;
      for (int time : times) {
        sum += mid/time;
      }
      if (sum >= n) {
        if (mid < answer) {
          answer = mid;
        }
        max = mid - 1;
      }
      else {
        min = mid + 1;
      }
    }
    return answer;
  }
}

이것은 이분 탐색 알고리즘은 제대로 사용한 코드이다. 우리는 정해진 심사대의 개수로, 정해진 사람수를 심사할 수 있는 최소 시간을 알아야한다.

 

이분 탐색을 이루는 min, max, mid가 있다. min 은 우리가 아직 최소 시간을 알지 못하니 0이나 1이 되면 되고,

max는 주어진 입국 심사대로 도출될 수 있는 가장 긴 시간을 설정하면 된다. 즉 가장 오래 걸리는 심사대 * n 하면 된다.

그러나 어떤 사람은 그냥 Long.MAX_VALUE로 max를 설정하기도 했는데, 어차피 주어진 조건으로 탐색 범위는 좁혀들테니 큰 문제는 없나보다.

 

최소 시간의 조건은 다음과 같다.

모든 심사대를 합하여 정해진 수만큼 심사할 수 있는 시간 중 최소가 되는 시간이다.

 

이 말은 다시

"각 심사대가 심사할 수 있는 사람 수를 합친 것 = 정해진 사람 수"를 만족하는 시간 중 최소 시간이 된다.

 

"각 심사대가 심사할 수 있는 사람 수를 합친 것 = 정해진 사람수"를 만족하는 시간은 이분 탐색으로 찾을 수 있다.

(여느 이분탐색처럼 일치할 때까지 min과 max의 값을 조정함으로써 범위를 조정하는 것이다.)

그 중 최소 시간을 찾을 수 있는 것일까?

 

이분 탐색 알고리즘을 살짝 변형하면 된다!

 

나도 아직은 정확히 와닿지는 않으나 mid가 원하는 조건을 만족할 때 반복문을 빠져나오지 않고, 찾았더라도 계속해서 범위를 아래로 좁혀나가며 최솟값을 찾는 것이다. 이 방법은 다음 코드로 구현이 된다.

      if (sum >= n) {
        if (mid < answer) {
          answer = mid;
        }
        max = mid - 1;
      }

이렇게 계속해서 발견해낸 값들 중 가장 작은 값만 answer에 저장한 후 결국 min 이 max를 넘어갈 때에서야 반복문을 빠져나오고 answer을 리턴한다.