[프로그래머스] 입국심사 - python 파이썬

문제

 

 

 

 

이 문제에서 가장 유의해야할 점은 주어진 값들의 제한 범위이다.

문제를 보면 알 수 있듯이 무려 n이 10억이하의 숫자이다 이 부분을 꼭 유의해서 풀이를 찾아야한다

 

 

그렇기때문에 이분탐색 을 사용하여 문제를 해결해주었다.

 

 

 

이분탐색이란?

 

자료의 중간값(mid)이 원하는 target값인지 비교해주면서 mid가 target이 아니라면 대소비교를 통하여 범위를 조정해가면서 target을 찾는 알고리즘이다.

 

 

 

하지만 이 문제에서 mid값을 어떤걸로 주어야하는 지에 대한 부분이 어려웠다

times 배열을 정렬해서 중간값을 준다해도 나누어 떨어질때를 구하는 것이기 때문에 times 내의 요소들의 순서가 우리가 구하고자하는 값의 순서와는 다르기 때문에 중간값으로 둘 수 없다.

 

 

해결방법

 

 

left = 1
#걸릴 수 있는 최대 시간
right = max(times) * n

 

 

바로 시작과 끝을 이렇게 두는 것이다

 

이때 right 값은 가장 오래 걸리는 심사관 * n을 해준 값이기때문에 n 명을 심사해줄 때 가장 오래 걸리는 경우이다.

 

그래서 mid는

 

mid = (left+right)//2

 

 

이렇게 되는 것이다

 

그리고 이 중간값을 times에 대한 반복문에서

 

mid // 각 심사관이 걸리는 시간

 

을 해준 값을 계속해서 people이란 변수에 저장해두면 중간 시간값인 mid 일때 몇명을 심사했는지 알 수 있다

 

 

 

정답 코드

def solution(n, times):
    answer = 0
    left = 1
    #걸릴 수 있는 최대 시간
    right = max(times) * n
    
    while(left<=right):
        mid = (left+right)//2
        people = 0
        
        for t in times:
            #현재 시간을 mid로 두어 전체 심사관이 몇명 심사했는지를 people에 더해줌
            people += mid//t
            
            #n명을 이미 다 심사 했다면 break
            if people >= n:
                break
        #n명이상으로 심사했을 때 범위 조정
        if people >= n:
            answer = mid
            right  = mid-1
        #n명 미만으로 심사했다면 범위를 조정
        else:
            left = mid + 1
                
        
        
    
    return answer

 

 

 

그리고 혹시 6번 테스트케이스에서 예외가 발생한다면 left <= right 여기서 부등호가 < 은 아닌지 확인해주면 된다

 

이 부분을 수정하여 정답을 받았다.