[프로그래머스] 이분탐색 - 입국심사 (level.3)

 

문제링크

 

나의 풀이

1. 이분탐색이라고 주어지지 않았을 경우에는 못풀었을 확률이 크다. 
2. 이분탐색 알고리즘 강의를 듣고 풀었다..... 어렵다 ㅠㅠ 

▶ 풀이설명

1. 이분탐색은 탐색하고자 하는 리스트가 정렬된 상태에서, 가장작은값(left), 가장큰값(right)로부터 mid값을 찾고, mid값과 비교해나가면서 최적값을 탐색하는 것이다.
2. 해당 문제에선 가장 최적의시간을 left, 가장 오래걸리는 시간을 right로 두고, 두 값을 더하고 2로 나누어준 값을 mid시간으로 정했다. 
3. mid시간을 times 리스트에 있는 값들을 사용해서 나누어주면, 해당 몫은 mid시간에 처리할수 있는 손님의 수를 의미한다. 만약 이 손님의 수가 n보다 크면 반복문을 나오게 된다. 손님의 수가 n보다 크다는 의미는, 제시된 손님의 수(n)을 충분히 케어 가능하다고 판단했기 때문이다.
4. 마지막에 mid타임으로 처리 가능한 손님의 수가 n보다 크면, 시간이 충분하다는 뜻이므로, 더 작은 시간대에서 최적의 시간을 찾아야 한다. 따라서 answer는 지금까지 구한 최적의 수인 mid로 바꾸어주고, right값을 mid-1로 정해주어 다시 값을 찾는다.
5. 만약 mid타입으로 처리 가능한 손님의 수가 n보다 작으면, mid타임으로는 손님을 케어할수 없다는 뜻으로 해석된다. 따라서 mid타임보다 더 충분한 시간대에서 최적의 시간을 찾아야한다. 따라서 최소시간으로 지정되어있던 left값을 mid바로 오른쪽값, mid+1 로 옮겨주고 다시 처음부터 과정을 반복한다.

def solution(n, times):
    left = 1 #가장 효율적인 시간을 left에 저장
    right = max(times) * n #가장 비효율적인 시간은 60초
    answer = 0

    while left <= right:
        # mid값을 구해주고, mid 보다 left가 크면 left를 mid로 설정하고 다시 초반부터 반복
        mid = (left+right) // 2 
        #mid time동안 얼마만큼의 손님을 받을 수 있는지 people 변수에 저장
        people = 0 

        for t in times:
            people += mid//t
            if people >= n :
                break

        # 만약 mid시간안애 처리하는 손님의 수가 n보다 크면 mid 보다 작은 공간에서 최적 수를 찾아야하므로
        if people >= n:
            answer = mid
            right = mid -1
        #만약 mid시간안에 처리하는 손님의 수가 n보다 작으면 mid보다 큰 시간대에서 최적수를 찾아야하므로 left를 옮겨줌
        elif people < n:
            left = mid + 1

    return answer

 

다른사람풀이

가장 좋아요를 많이 받은 풀이도 나처럼 푼 이분탐색형 풀이였다. 이분탐색에 대해서 조금 더 자세하게 공부를 해본뒤 이 문제를 다시 풀어보길 바란다. 꼭 ,,, 맞추자