99클럽 코테 스터디 3일차 TIL: 이분 탐색 반환값

오늘의 문제 | 프로그래머스: 입국심사

오늘은 처음으로 프로그래머스 문제가 출제되었다. 프로그래머스로 문제를 해결하는게 거의 처음이라 어색하고 문제 유형도 다르다고 느껴지긴 한다.

프로그래머스는 solution 함수 기반으로 돌아간다.

기본적으로 입력이 되어있는 함수에 입력값과 반환값이 적혀있다. 따라서 solution 함수의 출력값만 정상적으로 들어가게 하면 될 듯 하다.

아이디어: 답은 times 배열의 원소의 배수이다.

n의 범위가 매우 크고, 심사하는 시간도 매우 크기 때문에 이분탐색을 이용해야 하는건 맞다. 사실 프로그래머스는 타이틀에 알고리즘이 적혀있어서 보자마자 이분탐색임을 알 수 있었다.

1. 예시 설명에서 보았듯이 단순히 심사대가 비는 곳에 들어가는 형식이 아닌, 가장 빨리 마무리될 수 있는 시간을 구하는 것이다.
2. 중간에 심사대가 쉴 일은 없고, 마지막에 진행하지 않는 심사대만 존재하므로 어떤 수의 배수인건 확실하다.

걸리는 시간을 이분 탐색하여, 답이 될 수 있는 가장 작은 값을 찾는 것을 목표로 해야 겠다고 생각했다. 따라서 1부터 10억까지로 이분 탐색을 돌리려고 한다.

def check(times, time):
    answer = 0
    for i in times:
        answer += time//i
    return answer
# 해당 time만큼 돌렸을 때 최대로 통과할 수 있는 사람 수

def solution(n, times):
    left = 1
    right = 1_000_000_000
    mid = 0
    
    while 1:
        if left==right: break
        mid=(left+right)//2
        if check(times, mid)>=n:
            right=mid
        else:
            mid+=1
            left=mid
            
    
    answer = mid
    return answer

이 코드를 돌렸을 때는 몇몇 문제는 맞고 몇몇 문제는 틀린다. 분명 어제까지만 해도 이분탐색을 마스터한 줄 알았는데… 어떤 부분에서 문제가 생긴건 지 이해가 안간다. 계속해서 3 5 7 8 케이스가 틀렸다고 뜬다.

결국 너무 많은 시간을 쓰는거 같아서… 답지를 펼쳐보게 됐다. 답 코드는 아래와 같다고 한다.

# 정답 코드: 프로그래머스 제공
def solution(n, times):
    answer = 0
    start, end, mid = 1, times[-1] * n, 0

    while start < end:
        mid = (start + end) // 2
        total = 0
        for time in times:
            total += mid // time

        if total >= n:
            end = mid
        else:
            start = mid + 1
    answer = start
    return answer

이 코드를 보며 깨달을 수 있는 것들은 아래와 같다.

while 탈출 조건을 while 조건에 넣는다.

사실 나는 귀찮아서 따로 if문을 두어서 해결하는 편이다. end가 start와 같거나 작아질 때까지 반복을 돌린다는 건 동일하다. 물론 큰 차이는 없겠지만 식을 간단하게 해야하므로 쓸만해 보인다.

end값의 초기값을 최대한 작게 선언한다.

아무리 큰 케이스더라도 times의 가장 작은 원소 * n 번이 최대이다. 따라서 해당 숫자를 end로 둘 수 있다. 물론 답에는 영향없겠지만 시간을 줄이기 위해서 필요하다.

근데 아무리 봐도 코드가 비슷해보이는데 뭐가 문제인지 모르겠다. 비슷한 형식으로 변경하더라도 계속 틀렸다고 뜨긴 한다.

정답값을 left로 선언한다.

어째서 mid가 아니라 left인지 모르겠지만 정답 코드에서는 left로 반환했고, 실제로 이렇게 제출했더니 정답으로 떴다… 아무래도 mid로 변환해서 정답 반환하는 과정에서 값이 1씩 달라지나보다. 앞으로는 정답 반환하는 것도 바꿔가면서 해봐야겠다.

def check(times, time):
    answer = 0
    for i in times:
        answer += time//i
    return answer
# 해당 time만큼 돌렸을 때 최대로 통과할 수 있는 사람 수

def solution(n, times):
    left = 1
    right = times[-1]*n
    mid = 0
    
    while 1:
        if left>=right: break
        mid=(left+right)//2
        if check(times, mid)>=n:
            right=mid
        else:
            left=mid+1
            
    
    answer = left
    return answer

오늘의 회고

솔직히 다 깨달았다고 생각했는데 시간을 너무 쓴게 아쉽다. 그래도 정답값이 꼭 mid일 필요가 없다는 걸 깨닫기도 했고, 이분 탐색을 3일 연속으로 풀다보니 어느정도 겁도 사라진듯 하다.