프로그래머스 Lv.3 입국심사와 이진탐색

해결하지 못하여서 구글링하였다.
나는 완전탐색, 그리디, 이진탐색 문제들에 약한 것 같다.

입국심사

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(n, times):
answer = 0;
left,right=1,max(times)*n; # left는 최소시간 right는 최대시간
while(left<=right):
mid=(left+right)//2;
people=0;
for time in times:
people += mid //time; # mid 시간동안 심사한 사람의 수

if people>=n:
break;

# 검사할 수 있는 사람이 검사할 사람보다 많을 경우

if people >= n:
answer =mid;
right = mid - 1;

# 검사할 수 있는 사람이 검사할 사람보다 적을 경우

elif people<n:
left = mid + 1;

return answer;

로직은 다음과 같다.

  1. 최소시간(left)과 최대시간(right)을 정한다.
  2. 중간값인 (mid)시간에는 몇 명 검사할 수 있는지 검사한다.
    즉 mid를 기준으로 삼는다.
  3. n명 검사할 수 있을경우 right를 mid-1로, n명을 다 검사하지 못할 경우 left를 mid+1로 한다.

이는 mid값을 기준으로 각각의 경우에 해가 되는 right값은 mid의 왼쪽, 해가 되는 left값은 mid의 오른쪽에 위치하기 때문이다.

  1. right가 left보다 작아질 때 까지 반복한다.
    최대시간(right)이 최소시간(left)보다 작아졌다는 것은 이전 시행의 결과가 해라는 의미이다.

이진탐색

이진탐색은 기준을 정해놓고 범위를 줄여나가는 것이 핵심인 것 같다.

이 문제의 경우 n명을 검사해야 하므로 n명을 검사할 수 있는 범위를 구해 기준으로 하고 범위를 줄여나가는 방식으로 풀어야 했다.

정리

나와는 상성이 좋지 않지만 비슷한 유형의 문제를 풀다보면 풀 수 있을 것이라고 생각한다..!

댓글