[프로그래머스] LEVEL3 입국심사 (Python)

문제

문제 링크

문제 해결 접근

• 이분 탐색 문제 카테고리인데 도대체 어떻게 이분 탐색으로 접근해야할지 감조차 안잡혔다.
• 무엇보다 n이 매우 컸기 때문에 '이분 탐색'으로만!! 접근해야 할 것 같다는 생각이 들었다.
• 정말 모르겠어서 블로그 글을 통해서 힌트를 얻었다.

이분 탐색 알고리즘

• 이분 탐색의 기본 개념은 이해하기 어렵지 않으나, 코드로 구현하는 것이 어렵다. 약간의 실수만 있어도 반복문 안에서 영원히 빠져나오지 못 할 수 있기 때문에,,, 기본 코드를 외워놓는 것이 좋다.
  특히, 코테에서 탐색 범위가 매우 큰 상황이라면 O(logN)의 속도를 낼 수 있는 이진 탐색을 활용하는 것이 필요하다.
• 시간복잡도가 O(logN)인 이유는, 이진 탐색 알고리즘이 한 단계를 거칠 때마다 확인하는 원소가 평균적으로 절반이 줄어들기 때문이다.
  반복문으로 구현한 이진 탐색 코드는 아래와 같다.

def binaray_search(array, target, start, end):
	while start <= end:
    	mid = (start+end) // 2
        
        ## 찾은 경우 중간점 인덱스 반환
        if array[mid]==target:
        	return mid
        
        ## 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
        	end = mid - 1
        
        ## 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
        	start = mid + 1 

문제에 이분 탐색 알고리즘 적용하기

• 이분 탐색의 기본 아이디어가 아무래도 target 값이 mid와 일치할 때 반환한다, 이기 때문에 문제에 응용하여 접근하기가 쉽지 않았다.
• 이분 탐색 문제는 1) 이분 탐색의 범위 2) 이분 탐색의 기준을 정하는 것이 핵심이다.
  1) 본 문제 이분 탐색의 범위: 심사를 하는 데 총 걸릴 수 있는 시간
  2) 이분 탐색의 기준: 주어진 시간 동안 심사한 사람의 수가 n보다 많거나 같을 경우에는 시간이 충분하다는 의미이기 때문에 왼쪽 영역의 시간을 탐색하고, 주어진 시간 동안 심사한 사람의 수가 n보다 작을 경우에는 시간이 부족하다는 의미이기 때문에 오른쪽 영역의 시간을 탐색하게 해야 한다.

코드 구현

trial 1 (fail)

def solution(n, times):
    answer = 0

    ## 이분 탐색의 범위가 시간 리스트
    ## 최솟값은 1분, 최댓값은 가장 오래 걸리는 심사위원에게 n명이 모두 심사받는 시간 
    ## 우리는 이 리스트를 탐색하면서 최적의 시간을 확인할 것 
    time_list = [i for i in range(1, max(times)*n+1)]
    left = 0 ## 최솟값의 인덱스 
    right = len(time_list) - 1 ## 최댓값의 인덱스 

    while left <= right :

        ## 시간 리스트 중 중간 값을 임의로 잡자
        mid = (right+left) // 2
        current_time = time_list[mid]

        ## 현재 시간 안에서 심사를 받을 수 있는 인원
        people = 0 ## 심사 받은 사람의  수 
        for time in times:
            people += current_time // time 
            ## 심사 받은 사람의 수가 n 명보다 크다면 break
            if people >= n :
                break 

        ## 심사 받은 인원이 n명과 일치하면, 현재가 최적의 값이기 때문에 반환하기 
        if people == n:
            answer = current_time 
            break

        ## 심사 받은 인원이 n명보다 크면, 시간이 충분하다는 의미이므로 더 작은 시간이 가능한지 확인해보기 
        elif people > n:
            right = mid - 1

        ## 심사 받은 인원이 n명보다 작다면, 시간이 부족하다는 의미이므로 더 많은 시간이 필요한지 확인해보기
        elif people < n :
            left = mid + 1

    return answer

• 먼저 시간 초과가 떴다. 왜냐하면! 바보같이 O(N)의 리스트를 굳이 만들어줬기 때문이다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
• 이분 탐색 = 리스트라고 생각해서 생긴 실수였다. logN을 구현하는 것이 목표이기 때문에 당연히 시간 초과가 떴다!
• 리스트 없이 구현하는 방법 => 범위를 정해서 left, right 변수에 넣어준 다음에 mid를 계속 찾아나가게 만들어주면 된다.

trial 2 (fail)

def solution(n, times):
    answer = 0

    ## 이분 탐색의 범위가 시간 리스트
    ## 최솟값은 1분, 최댓값은 가장 오래 걸리는 심사위원에게 n명이 모두 심사받는 시간 

    left = 1 ## 입국 심사에서 걸리는 최소의 시간 
    right = max(times)*n ## 입국 심사에서 걸리는 최대의 시간 

    while left <= right :

        ## 중간값을 임의로 잡는다고 할 때 
        mid = (right+left) // 2

        ## 현재 시간 안에서 심사를 받을 수 있는 인원
        people = 0 ## 심사 받은 사람의  수 
        for time in times:
            people += mid // time 
            ## 심사 받은 사람의 수가 n 명보다 크다면 break
            if people >= n :
                break 

        ## 심사 받은 인원이 n명과 일치하면, 현재가 최적의 값이기 때문에 반환하기 
        if people == n:
            answer = mid 
            break

        ## 심사 받은 인원이 n명보다 크면, 시간이 충분하다는 의미이므로 더 작은 시간이 가능한지 확인해보기 
        elif people > n:
            right = mid - 1
        
        ## 심사 받은 인원이 n명보다 작다면, 시간이 부족하다는 의미이므로 더 많은 시간이 필요한지 확인해보기
        elif people < n :
            left = mid + 1
        
    return answer

• 시간 초과를 해결했는데 정답이 틀렸다.
• 그 때 찾은 반례 테스트 케이스는, n=6 times=[2, 5] return=10 이었다.
  현재 코드는 people과 n의 값이 온전히 같을 때에만 answer를 mid로 놓고 정답으로 반환하지만, 실제로는 people이 n보다 큰 경우에도 정답이 될 수 있다.
• 10분 동안 10//2 = 5명과 10//5=2명 총 7명을 심사할 수 있는데, 이것이 정답이 될 수 있는 것이다. (왜냐면 9분이 되면 총 5명밖에 심사할 수 없기 때문에 결국 10분이 필요하다.)
• 그래서 심사 받은 인원이 n명보다 클 때 answer가 n과 같아져야 하지만, 최적의 경우가 있을 수 있으므로 끝까지 탐색하도록 코드를 수정하였다. (왜냐면 11분일 때도 7명 심사 가능하지만, 1분 더 줄일 수 있기 때문이다.)

trial 3 (pass!)

def solution(n, times):
    answer = 0
    ## 이분 탐색의 범위가 시간 리스트
    ## 최솟값은 1분, 최댓값은 가장 오래 걸리는 심사위원에게 n명이 모두 심사받는 시간 

    left = 1 ## 입국 심사에서 걸리는 최소의 시간 
    right = max(times)*n ## 입국 심사에서 걸리는 최대의 시간 

    while left <= right :
        ## 중간값을 임의로 잡는다고 할 때 
        mid = (right+left) // 2

        ## 현재 시간 안에서 심사를 받을 수 있는 인원
        people = 0 ## 심사 받은 사람의  수 
        for time in times:
            people += mid // time 
            ## 심사 받은 사람의 수가 n 명보다 크다면 break
            if people >= n :
                break 

        ## 심사 받은 인원이 n명보다 같거나 크면, 시간이 충분하다는 의미이므로 더 작은 시간이 가능한지 확인해보기
        ## 현재 값이 최적일 수 있으므로 answer = mid로 넣어주기 
        if people >= n:
            answer = mid 
            right = mid - 1

        ## 심사 받은 인원이 n명보다 작다면, 시간이 부족하다는 의미이므로 더 많은 시간이 필요한지 확인해보기
        elif people < n :
            left = mid + 1

    return answer

• 수정 사항을 반영하였고, 통과했다! 얏호!
• 심사 받은 인원이 n명보다 같거나 큰 경우 계속 최적의 시간을 탐색할 수 있도록 하였고, 더 이상 탐색할 수 없는 상황이 오면 (left > right) answer를 현재의 mid로 반영하기 위하여 코드를 수정해주었다.

느낀 점

• 이분 탐색을 응용해서 문제 푸는 것이 생각보다 어려웠다.
• 다른 이분 탐색 문제를 과연 다음번에도 해결할 수 있을지!!
• 기억 해야 할 사항: 숫자가 커서 O(n)보다 작아야 할 때는 이분 탐색, 이분 탐색에서 가장 중요한 것은 이분 탐색의 범위와 이분 탐색 범위를 결정할 기준!