프로그래머스 [Lv. 3] 입국심사 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(n, times):
    answer = 0
    
    # times가 정렬되어 있다고 가정하고
    minTime = min(times)
    maxTime = max(times) * n
    
    while minTime <= maxTime:
        middleTime = (maxTime + minTime) // 2
        numberOfPeople = 0
        
        for time in times:
            numberOfPeople += middleTime // time
            
            if numberOfPeople >= n:
                answer = middleTime
                maxTime = middleTime - 1
                break
        else:
            minTime = middleTime + 1
            
    return answer

풀이 방법

1. max와 min을 통해서 가장 적게 걸릴 수 있는 예상 시간과 가장 오레 걸릴 수 있는 예상 시간을 정한다.
   1. maxTime = times[-1]로 할 수도 있지만
      1. 정렬이 되어있다는 가정하에 -1이 가장 큰 시간
      2. 하지만 이렇게 되면 O(n)의 시간 복잡도를 가진다.
      3. max, min을 사용하면 O(logN)의 시간 복잡도를 가지므로 더 빠르다.
2. 사람 수를 계산해주면서 n보다 크거나 같은 시간을 찾는다.
   1. 이 과정에서 이진탐색을 활용한다.
3. 출력한다.

느낀점

• max나 min sort의 시간복잡도를 생각하고 풀어야 한다는 것을 알았다.