[프로그래머스] Swift - 입국심사

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

프로그래머스

 

2023.07.25 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

n명의 사람들을 전부 심사해야 하는데 걸리는 최소 시간을 구하는 문제입니다.

주어진 조건에서 n의 크기와 심사에 필요한 시간이 1,000,000,000으로 매우 크기 때문에 완전 탐색으로 접근할 시 무조건 시간 초과가 발생할 것이라는 것을 염두하고 시작했습니다.

 

결국 핵심은 "최소 시간"을 구하는 것입니다. 주어진 심사관들은 고정이기 때문에 시간 값을 바꾸면서 몇명을 처리할 수 있는지 체크하면 됩니다.

즉, 이분 탐색으로 시간의 범위를 줄여나가면서 n명을 처리하는데 걸리는 최소 시간을 찾으면 됩니다.

 

입출력 예시

n	times	return
6	[7,10]	28

위와 같은 예시에서 심사관 중 가장 일처리가 오래걸리는 사람은 10초가 걸립니다.

따라서 6명을 심사하는데 최악의 경우 6*10초가 걸리게 됩니다.

start = 0, end = 60으로 두고 이분 탐색을 시작하면 됩니다.

 

mid = (0+60)/2 = 30입니다.

30분이 주어졌을 때 0번째 심사관은 최대 30/7 = 4명을 심사할 수 있고,

1번째 심사관은 30/10 = 3명을 심사할 수 있습니다.

총 7명을 심사할 수 있는 것이죠!

 

하지만 우리는 6명만 심사가능해도 충분하기 때문에 end값을 조정하여 시간을 줄입니다.

start = 0, end = 29로 두고 다시 계산하면 이번에는 3명만 심사가 가능합니다.

 

6명에 못미치는 수이기 때문에 start를 늘려서 다시계산합니다.

 

이 과정을 반복문으로 반복하면 됩니다.

 

 

문제 조건 중에서 더 빨리 끝나는 심사대가 있으면 기다렸다가 거기서 심사를 받을 수 있다는 조건이 있어서 이 부분도 별도로 처리해줘야 하나 생각할 수 있지만 이 사항은 저절로 충족됩니다.

앞선 로직은 각 심사대가 쉬지 않고 계속 일하는 것을 전제로 계산을 하게 됩니다.

따라서 더 빨리 끝나는 심사대(times가 작은 심사관)가 쉬지 않고 일하기 때문에 주어진 시간동안 처리 가능한 최대 사람 수가 도출됩니다. 즉, 가장 빨리 끝나는 심사대가 있으면 기다린다 == 가장 빨리 끝나는 심사대가 쉬지 않고 일할 수 있도록 한다.

이렇게 해석할 수 있습니다!

 

풀이

fileprivate func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var start = 0
    var end = times.max()! * n
    
    while start <= end {
        let mid = (start+end) / 2   // 시간 (이분 탐색 대상)
        var cnt = 0     // 주어진 시간(mid) 동안 처리 가능한 사람의 수
        
        for time in times {
            cnt += mid / time
        }
        
        if cnt >= n {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    
    return Int64(start)
}

end의 초기값을 Int.max로 두면 런타임에 core dumped 에러가 발생하는 테스트 케이스가 존재했습니다.

cnt에 더할 때 overflow가 발생하기 때문입니다.

 

따라서 주어진 값들을 기반으로 최대 시간을 구해서 end를 설정했습니다.

심사관 중에서 일처리가 가장 오래 걸리는 시간을 기준으로 n명을 곱한 것이 그것입니다.

 

 

마무리

이분 탐색 문제는 항상 풀이는 간단하지만 개인적으로 이분 탐색이라는 아이디어를 떠올리는 것이 어려운 것 같습니다.

시간 복잡도가 O(logN)으로 매우 낮기 때문에 문제 조건에서 크기가 큰 값들이 있다면 이분 탐색을 떠올리는 습관을 가지면 좋을 것 같습니다!

그리고 다른 조건들이 다 고정인 상황에서 하나의 최솟값을 구할 때 이분 탐색이 유용하다는 점도 기억하면 좋을 것 같네요!