[프로그래머스] 입국심사(LEVEL 3)

문제링크

문제접근 ❓

• 이분탐색
  💡 심사하는 시간은 1부터 max(times[i]) * n 까지 존재한다. 모든 사람을 심사할 수 있는 최소 시간을 찾는 것이 이 문제의 해답이다. 1 ~ max(times[i])*n 사이의 적절한 값을 찾아야 하고 상수값의 범위가 10억 이기때문에 굉장히 크게 주어질 수 있는 상황이다. 따라서 최대한 시간을 단축해야하는 문제이다. 그래서 이진탐색으로 1 ~ max(times[i])*n 사이에서 값을 찾는 것이다. mid 값을 통해서 mid 시간안에 처리할 수 있는 총 사람수를 구하고 (mid / times[i] 연산을 통해서) [해당시간안에 처리할 수 있는 사람 수] 와 [목표 사람수]를 비교한다.

[처리할수 있는 사람수]가 [처리해야되는 사람수]보다 많으면 시간을 너무 여유있게 잡았음 → 시간을 줄여봄  
[처리할수 있는 사람수]가 [처리해야되는 사람수]보다 적으면 시간을 너무 빡빡하게 잡았음 → 시간을 늘려봄

오답노트 ❓

• 오답 코드

  class Solution {
      public long solution(int n, int[] times) {
          long answer = 0;
          long min = 1;
          long max = 1;
  
          for (int time : times) {
              max = Math.max(time, max);
          }
  
          max *= n;
  
          // System.out.println(max);
  
          while (min <= max) {
              long mid = (min + max) / 2;
              long sum = 0;
  
              for (int time : times) {
                  sum += mid / time;    
              }
  
              if (sum >= n) {
                  max = mid - 1;
              } else if (sum < n) {
                  min = mid + 1;
              } else {
                  answer = mid;
                  break;
              }
          }
  
          return answer;
      }
  }

• 틀린 이유
  ❌ 현재 걸리는 시간 mid 에대해서 처리할 수 있는 인원 sum 을 계산하는데 해당 시간으로 처리할 수 있는 사람의 수 (sum) 가 n (처리하려는 사람의 수) 보다 클 때와 같을 때 조건을 나누어서 생각했는데 sum < n 으로 시간이 부족한 경우를 제외하고는 해당 시간으로 최솟값 갱신만 하면된다... sum == n 으로 딱 안나오는 경우에는 .. answer = 0 으로 반환해버려서 틀렸다고 나왔다...

---

Solution

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        long min = 1;
        long max = 1;

        for (int time : times) {
            max = Math.max(time, max);
        }

        max *= n;

        // System.out.println(max);

        while (min <= max) {
            long mid = (min + max) / 2;
            long sum = 0;

            for (int time : times) {
                sum += mid / time;    
            }

            if (sum < n) { // 시간이 부족한 경우
                min = mid + 1; // 최소시간 갱신
            } else { // 시간이 충분한 경우
                max = mid - 1; // 이분탐색으로 끝까지 최소시간을 탐색
                answer = mid;
            }
        }

        return answer;
    }
}