[프로그래머스] 이분탐색 _ 입국심사 (파이썬, level3)

https://programmers.co.kr/learn/challenges

코딩테스트 연습

 

 

문제설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

 

 

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

 

입출력 예

 

 

n            times                   return

6

[7, 10]

28

 

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에

첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

 

---

 

 

사고 과정

 

일단 데이터가 진짜 오지게 크다는것을 확인할 수 있다.

데이터가 클땐 우리는 이분탐색을 사용해야한다는것을 직감적으로 알 수 있다. 

 

 

저번에 한참 이분탐색을 풀때 깨달았던 점은

어찌되었던 이분탐색은 start와 end를 잘 설정해야한다는 점.

그리고 mid는 return 받기 원하는 정보에 관한 데이터라는 점이다.

 

 

 

이 문제에서 return 받기 원하는 정보를 읽어보자.

 

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 

 

 

이정보를 통해 (start+end)//2 로 결정되는 mid 값은 심사를 받는데 걸리는 시간이 된다. 

 

그렇다면 start 와 end도 시간에 관한 정보임을 확신할 수 있다. 

 

start는 시간의 최소값으로 1

end는 최대로 걸리는 시간을 계산해야한다.

times에서 최대값은 제일 늦게 심사하는 심사관의 1명당 걸리는 시간이고

그사람에게 n명이 전부 심사를 받았을 때 최대로 걸리는 시간이 된다. 

 

 

res = end를 해준것은 최대값을 res에 저장해놓고, 더 적은 시간이 걸리는 케이스가 있으면 비교해 업데이트 해주기 위함이다. 

 

 

 

 

start,end = 1, max(times) *n 
res = end
while start <= end:
	mid = (start + end) // 2

 

 

이후에 이분탐색 코드 안에서 어떤것을 해야하는지 생각해야한다.

 

먼저 mid는 심사를 받는데 걸리는 시간  이 되어야하는데 

mid 안에 n명이 검사할 수 있는건 맞을지 체크를 해줘야한다. 

 

times의 각 time을 mid // time을 하면 mid라는 시간동안 각 심사관이 심사할 수 있는 사람의 수를 구할 수 있다. 

 

전체를 다 더했을 때 people이 n보다 작으면 mid(심사받는대 걸리는 시간) 가 증가해야하고, 

people이 n보다 크거나 같으면 mid 가 감소해서 테스트 해야 한다.

 

people이 n보다 크거나 같은 경우에 res와 mid값을 비교해서 더 작은값을 res에 할당하는데

이 이유는 people이 크거나 같을 때마다 최소값이 갱신될 수 있으니까 ...! 

 

people 이 n보다 작은경우는 애초에 모든 사람을 검사할 수 없는 것이므로 res가 될 수 없다. 

 

 

 

정답 코드

def solution(n, times):
    
    start,end = 1, max(times) *n 
    res = end
    while start <= end:
        mid = (start + end) // 2
        
        people = 0
        for time in times:
            people += (mid // time)
            
        if people < n:
            start = mid+1
        else: #people >= n:
            end = mid-1
            res = min(res, mid)
            
    return res