프로그래머스_Lv3 입국 심사 풀이 복기

문제 요약

• n: 입국 심사를 기다리는 사람의 수는 최대 10억
• times: 각 심사관이 한 사람을 심사하는 데 걸리는 시간이 최대 10억, 심사관 수는 최대 10만

=> 음.. 조건이 일단 그리디나 조합은 안될 것 같다.

 

🍎 주요 포인트

• 심사관들은 동시에 여러 명을 처리할 수 있는 병렬 처리 형태이다.
• 각 심사관은 주어진 시간동안 한 사람씩 심사한다.

 

핵심 아이디어

최소 시간은 min(times) ~ 최대 시간은 max(times) * n (= 최악의 경우 한 심사관이 모든 사람을 처리)
따라서, 효율적인 탐색이 필요하다.

 

결정 문제로 전환

특정 시간 내에 모든 n명의 심사가 가능한가? 라는 결정 문제로 전환하기!
심사 가능 여부에 따라 특정 시간을 늘리거나 줄이면서 가능한 시간을 찾자 => 이분 탐색

=> 이분 탐색으로 최적의 최소 시간을 찾는다. 조건 검사를 고민해본다.

 

구현 로직 결정

1. 이분 탐색 범위 설정하기

• 최소 시간 ~ 최대 시간

2. 이분 탐색 수행하기

1) 중간 시간 계산 (탐색 시작할 곳)
2) 해당 시간 내에 심사 가능한 인원 계산 (각 심사관의 가능 인원을 합산)
3) 조건에 따라 범위 이동
   3-1) 가능 인원이 n 미만이면, 해당 시간 내에 불가능하다! => 시간을 늘린다. left = mid + 1
   3-2) 가능 인원이 n 이상이면, 해당 시간 내에 가능하다!
       => 일단 이 값을 확보하고, 더 짧은 시간이 가능한가 찔러보자!
       => 시간을 줄인다. right = mid - 1
4) 종료 조건은 이분 탐색 완료 시 (left <= right)

 

🌟 기억할 부분!!

1. 결정 문제로 변환하기

• "이 시간 내에 모든 심사가 가능한가?" 로 바꾸면, yes or no로 판단 가능하다.

2. 이분 탐색 패턴은 무엇일까?

• 이 문제는 이분 탐색의 결정 문제 (Parametric Search) 유형이다.
• "최소 시간", "최대 길이", "최소 비용" 등 다양한 유형에 활용할 수 있다. => 조건 만족 여부로 판별할 수 있을까 생각해보자.

 

⛑️ 주의할 부분

1. 반복문 설정

while(left <= right){
     long mid = (left + right)/2;
      // 2. 각 심사관별 처리 가능한 인원 구하기 => 총 처리 가능 인원
     long cnt = 0;
     for (int i=0; i<size; i++){
         cnt += mid/times[i];
     }

     if (cnt < n) {
         // 3-1. n명보다 적으면 mid 시간 늘리기
         left = mid+1;
     } else if (cnt >= n){
         // 3-2. n명보다 크거나 같으면 일단 현재 값 저장하고, mid 시간 줄이기
         answer = mid;
         right = mid -1;
     }
    }

• 반복 조건 : left <= right
• 조건 분기 설정 : 처음에는 if문 분기를 3개로 했다. (cnt < n / cnt > n / cnt == n)
  => cnt >= n 으로 해주어야 한다. 시간이 짧아질 수 있을만큼 짧아져야 하기 때문에 (최소 시간)

 

2. 데이터 타입 오버플로우

long 으로 해주어야 할 부분을 모두 long으로 했지만 실패했다.
times 배열이 int 였는데 times의 원소와 연산하는 부분이 있었기 때문에 결과값이 int로 변환되었고 오버플로우가 발생해버렸다.

long left = times[0];
long right = (long)times[size-1] * n;

 

복습 포인트

항목	예시
이분 탐색 범위	left = 1, right = max값 * 개수
mid 계산	mid = (left + right) / 2
조건	if (조건 만족) → answer 저장하고 right = mid - 1
자료형	long (int 주의)

 

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