99클럽 코테 스터디 13일차 TIL, 프로그래머스 / 입국심사

🔑 오늘의 학습 키워드 : 이분 탐색

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=python3

def solution(n, times):
    left = 1
    right = max(times) * n
    
    while left < right:
        mid = left + (right - left) // 2
        done = 0
        
        for time in times:
            done += mid // time
        
        if done >= n:
            right = mid
        else:
            left = mid + 1
    
    return left

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

시간 복잡도가 괴랄한 것을 보니 이것은 떠오르는 대로 풀면 안되고

 

알고리즘을 활용해서 풀어야한다는 생각이 들었다.

 

시간 별로 처리할 수 있는 심사처리량이 있을테니

 

이분 탐색을 활용해서 시간 기준으로 처리할 수 있는 최소 시간을 return 하는 함수를 작성하면 되겠다고 생각했다.

 

⏰ 예상 시간 복잡도 O( M * log ( M * N))

M은 times의 길이 , N은 사람의 수

N = 10 ^ 9

M = 10 ^ 5

M * log ( M * N) = 1.4 * 10 ^ 6

제한 사항

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

😎 알고리즘 개요

left(최소)를 1로 두고, right(최대)를 배열 내의 있는 가장 큰 수 * n(가장 오래걸리는 경우)으로 설정을 했다

 

- mid 값 설정

mid = left + (right - left) //2 로 중간 값을 설정했는데 이는 파이썬에서는 사실 큰 상관은 없지만

 

다른 언어에서 문제를 풀 때 int형의 자료형에서 overflow가 날 수 있기 때문에 습관으로 썼다.

 

그 이유는 - 2,147,483,647  ~ 2,147,483,647 가 int 범위인데 중간 값을 찾기 위해서 

 

( left + right ) // 2를 하게 된다면 저 범위를 넘어가는 경우가 생기기 때문에 

 

left + (둘의 차이)//2를 하여 방지할 수 있다. 

 

- done 

처리한 사람들을 더해 나가는 변수

 

10분에 처리할 수 있는 사람은  [3, 5] 인경우

 

done += 10 %3 

done += 10 %5 

 

이렇게 된다.

 

- right, left 재 할당

그리하여 만약 너무 많은 사람을 처리해버렸다면 right를 mid로 바꾸고

 

너무 적은 사람을 처리한다면 left를 mid + 1로 바꾼다.

 

그 이유는 mid가 이미 충분하지 않은 시간이기 때문에 현재의 mid 값이 아닌

 

mid + 1을 통해 다음 값부터 찾아나갈 수 있다.

 

✅ 오늘의 회고

- 이분 탐색이라는 카테고리가 없었어도 이걸 풀 수 있었을까?

 

- 파이썬 bisect 모듈이 있는데 그걸 활용해서 풀어볼까?

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL