[Algorithm/Swift] 프로그래머스(Lv.3) - 입국심사

안녕하세요 제인입니다!

요즘은 프로그래머스의 문제들을 꾸준히 풀면서 취약한 유형의 문제들을 프로그래머스, 백준에서 더 찾아서 연습해보는 방식으로 PS 실력을 꾸준히 향상시키려고 노력하고 있는데요, 오늘은 저번에 <프로그래머스(Lv.3) - 징검다리 건너기> 문제를 통해 이분탐색 문제를 처음 접하고, 더 연습해보고 싶어서 프로그래머스에서 이분탐색 연습문제를 찾아서 풀어봤습니다!

풀다보니 징검다리 건너기 문제와 비슷한 점이 많은 것 같아서 이분탐색 문제를 접했을 때 접근하는 방법에 대해 기록해두면 좋을 것 같아서 가져와봤습니다 :)

문제 링크

프로그래머스

문제 풀이

일단, 이분탐색 문제로 분류되어 있으니 당연히 이분탐색으로 처음부터 풀었습니다.

제가 풀이한 방법을 먼저 정리하고, 카카오 기출문제인 <징검다리 건너기> 와의 공통점을 정리하면서 이분탐색 유형인지 어떻게 파악할 수 있는지, 그리고 이분탐색 유형 접근하는 방법에 대해 적어볼게요!

 

문제에서 구하라고 한 값은 모든 사람이 심사를 받는데 걸리는 시간의 최솟값입니다.

그렇기 때문에 '시간'을 기준으로 두고 최대 범위부터 반씩 좁혀나가는 방식으로 풀어야겠다고 생각했습니다!

left 변수는 1로, right 변수는 n * times.max()! 으로 초기화해두고 이분탐색을 진행했는데요,

탐색의 범위를 이렇게 설정한 이유는 심사를 가장 비효율적으로 오래걸리도록 하는 방법은 '가장 오랜시간동안 심사하는 심사관에게 모든 사람이 심사받는 경우' 이기 때문입니다! 

 

탐색 진행 방법은 다음과 같습니다.

1. 체크할 시간을 left~right의 중앙값으로 설정합니다. (mid 변수)
2. 기준 시간인 mid분 동안 심사할 수 있는 사람 수의 총합을 구합니다.
3-1. 2에서 구한 사람 수가 n(=심사해야하는 사람 수)보다 크거나 같으면 -> 새로운 right를 mid로 설정합니다. (방금 확인한 값이 최소 심사시간일 수도 있고 더 클 수도 있기 때문)
3-2. 2에서 구한 사람 수가 n(=심사해야하는 사람 수)보다 작으면 -> 새로운 left를 mid + 1로 설정합니다. (모든 사람 심사 위해서는 시간을 더 늘려야 하기 때문)
4. 1~3의 과정을 left와 right가 같아질 때까지 반복합니다.

Swift 풀이 코드

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var left = 1
    var right = n * times.max()!
    
    while left < right {
        var mid = (left + right) / 2
        var people = 0
        
        for i in 0..<times.count {
            // mid 시간동안 심사할 수 있는 사람 수
            people += mid / times[i]
        }
        
        if people >= n { // 통과 인원 같거나 많으면 -> 최소 심사 시간일수도 있고 더 클 수도 있음
            right = mid 
        } else { // 통과 인원이 더 적다면 (다 못 통과한 경우)
            left = mid + 1 // 더 긴 시간 필요
        }
    }
    
    return Int64(left)
}

이분 탐색을 시도해보면 좋을 문제

이분 탐색 문제는 해당 문제가 이분 탐색 유형인지 파악하고, 조건만 잘 설정한다면 그리 어렵지 않게 풀 수 있는 문제라는 생각이 들었는데요, 그래서 징검다리 건너기 문제와 이 문제의 공통점을 정리해보면서 이분 탐색을 시도해보면 좋을 문제들의 특징을 찾아보겠습니다!

 

1. 범위 내에서 구할 수 있는 최댓값 or 최솟값을 구하는 문제

이분 탐색 자체가 범위를 설정해놓고 반씩 줄여나가면서 최적의 해를 찾아가는 알고리즘이다보니, 당연히 문제에서 특정 범위를 설정해주고 여기서 구할 수 있는 최댓값 혹은 최솟값을 구해라! 이렇게 주어지는 문제에 적용할 수 있을 것 같습니다.

징검다리 건너기 문제는 주어진 길이의 징검다리를 건널 수 있는 최대 인원의 수를 구하는 문제였고, 이 문제는 n명을 심사하는데 걸리는 최소 시간을 구하는 문제였습니다!

 

2. 제한 사항으로 굉장히 큰 범위가 주어지는 문제

요것이 큰 특징인 것 같은데요, 범위가 작다면 완전탐색으로 경우 하나하나를 따져가며 최솟값 혹은 최댓값을 업데이트 시켜주면서 답을 구할 수 있겠지만 엄청 큰 범위를 다 확인해봐야한다면 굉장히 오랜시간이 걸리기 때문에 효율성 면에서 좋지 않은 코드가 됩니다..🥲

완전탐색에서 시간초과가 난다면 이분 탐색을 이용해서 코드를 더 효율적으로 개선할 수 있겠죠?? 만약 제한사항에 말도 안되는 범위가 주어진다면 처음부터 이분 탐색으로 접근하면 좋을 것 같습니다!!

 

요 두 문제의 경우에도 다음과 같이 엄청난 범위가 제한 사항으로 주어졌습니다. (심사시간 10억분 이러네요 10억분이면 1900년 걸림)

- stones 배열의 크기는 1 이상 200,000 이하입니다.
- stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.

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

 

3. 순서대로 조건을 설정해서 체크해보기가 어려운 문제 (다양한 경우의 수가 있을 수 있는 문제)

저는 두 문제의 특징이 단순히 조건문으로 확인해보기가 어려운 문제라고 느꼈는데요,

징검다리 건너기 문제 같은 경우 어떤 돌을 먼저 밟느냐에 따라서 건널 수 있는 인원의 수가 달라지기 때문에 가능한 모든 순서의 경우를 찾아서 체크해보기가 어렵습니다. (범위가 넓은 경우는 더더욱!) 그리고, 이 문제도 특정 시간이 되었을 때 어떤 심사대가 비어있어도 소요시간이 더 짧은 심사대가 빌 때까지 기다려서 심사받을 경우 더 짧은 소요시간이 나올 수도 있기 때문에 가능한 경우의 수를 모두 체크해주기가 여렵다고 느꼈어요.

이렇게 가능한 경우의 수를 하나씩 따져서 최적의 답을 구하는 것이 어렵다면, 거꾸로 최종적으로 구해야 하는 것(= 인원 수, 소요시간)을 기준으로 설정하고 이것이 최적의 해인지 체크해나가는 방법으로 풀 수 있겠다! 고 느꼈습니다.

---

저의 주관적인 관점으로 이분 탐색을 시도해보면 좋을 문제들의 특징을 한 번 뽑아봤는데요,

저도 아직 많은 문제를 풀어보지 못해서 요런 조건들이 적용되지 않는 문제들도 있을 수 있겠지만, 다양한 문제들을 풀면서 요런 문제는 이 알고리즘으로 접근하면 좋겠다! 하는 감을 익혀가는 것이 중요한 것 같아요. 결론은 문제를 많이 풀어보자!