[프로그래머스] 이분탐색 1. 입국심사

문제

출처: 프로그래머스

---

풀이

일단 이분탐색이나 시간은 생각하지 않고 막 짜보기로 했다.

입국심사대에 다음 사람을 받아 걸리는 시간을 계산하여 가장 적은 쪽으로 이동하게 한다.

def solution(n, times):
    curTime = [0 for i in range(n)]
    
    while(n > 0):
        curMin = curTime[0] + times[0]
        curIndex = 0
        for i in range(1, len(times)):
            if curMin > curTime[i] + times[i]:
                curMin = curTime[i] + times[i]
                curIndex = i
        
        curTime[curIndex] += times[curIndex]
        n -= 1
    
    return max(curTime)

4번 케이스부터 시간초과로 실패했다.

def solution(n, times):
    time = 0
    
    while True:
        time += 1
        curN = 0
        
        for i in times:
            curN += int(time / i)
            
        if curN >= n:
            break;
    
    return time

혹시나 해서 시간을 기준으로 다시 해봤는데 얜 3번부터 실패 😢

 

이분탐색이란 정렬된 배열에서 가운데 값을 기준으로 탐색 범위를 반씩 줄여가는 것으로 O(log n)의 시간복잡도를 갖는다.

문제는 어떤 값을 이분탐색해야하는지 감이 잘 안 잡힘,, 배열이랄게 times밖에 없어 더 고민이 됐다.

결국 검색하다가 시간을 이분탐색한다는 결정적 힌트를 봤다.

 

시간기준으로 풀었던 두번째 코드에선 time += 1씩 했는데,

이번엔 최대를 정하고 그 사이에서 이분탐색해보자

def solution(n, times):
    start = 0
    end = max(times) * n
    time = int(end / 2)

    while True:
        curN = 0
        for i in times:
            curN += int(time / i)
        
        if curN > n:
            end = time
            time = int((start + end) / 2)
        elif curN < n:
            start = time
            time += int((end - start) / 2)
        else:
            time = findMinTime(time, n, times)
            break
    
    return time

#n명이 통과하는 시간 중 가장 적은 시간을 찾기 위함
def findMinTime(time, n, times):
    curN = n
    
    while curN == n:
        curN = 0
        time -= 1
        for i in times:
            curN += int(time / i)

    return time + 1

세개에서 실패 ,, 나는 기준을 n명으로 두고 같으면 선형탐색했는데, 끝까지 이분탐색을 해야하나보다.

 

while문 조건에 =을 빼먹어서 한참 고생하다가 다른사람의 코드를 보고 수정했다.,,

그리고 전 코드는 int()로 소숫점을 내렸는데, // 를 사용하면 더 직관적으로 같은 기능을 수행할 수 있었다.

def solution(n, times):
    start = 0
    answer = 0
    end = max(times) * n

    while end >= start:
        time = (end + start) // 2
        curN = 0
        
        for i in times:
            curN += time // i
            if curN > n:
            	break
        
        if curN >= n:
            answer = time
            end = time - 1
        elif curN < n:
            start = time + 1
        
    return answer