[프로그래머스] (Swift) 입국심사 (lv.3, 파라메트릭 서치)

이분탐색과 파라메트릭 서치의 차이점과, 어느 때에 사용하면 좋은지에 대해서 명확하게 알고 넘어갈 필요가 있다고 생각된다. 맨 밑부분에 이 문제가 왜 파라메트릭 서치로 풀리는지에 대해서 생각을 적어놨다. 그것을 항상 기억하자!

 

⚫️ 문제

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

프로그래머스

 

⚫️ 나의 풀이

이거 바로 직전에 푼 문제와 매우 비슷햇기 때문에 금방 풀 수 있었다. (바로 이전에 풀었던 문제 아래 백준의 공유기설치)

https://didu-story.tistory.com/434

[백준] (Swift) 2110번 - 공유기 설치 (골드4, 이분탐색)

이분탐색의 문제 유형이 이런식인건가? 아직 사실 이분탐색의 문제 유형을 완벽하게 파악하지 못했다.
그냥, 이분탐색으로 문제가 분류되어있으니 이분탐색으로 풀었을뿐 ㅠㅠ 
탐색을 진행하는 부분에 있어서 범위가 크다면 이분탐색을 의심(?)해봐야겠다. (이 문제도 범위가 10억이다)

공유기설치 문제에서 '거리'를 기준으로 left, right, mid를 설정했었다. 원래 이분탐색의 가장 기본적인 형태로는 idx를 기준으로 하나씩 탐색하는 느낌이었는데 이렇게 '거리'나 '시간'을 기준으로 left, right를 설정해 주어야하는 문제들이 다수 출제되나보다! 익혀두자.

 

이 문제는 그래서 , 최적의 경우를 left로 두고, 최악의 경우로 right에 두었다. 주어진 예제로 보면

입국심사가 필요한 총 인원 n = 6
각 입국심사관이 입국심사를 하는데 걸리는 시간 times = [7, 10]

입국심사가 필요한 총인원은 신경쓰지 않고 가장 최적의 경우는, 단 1분만 걸려서 모든 심사를 완료하는 경우일 것이다. (이렇게 거리나 시간을 기준으로 이분탐색을 진행하는 문제는 대부분 left는 1부터 시작한다. 

그리고 right는 가장 최악의 경우를 담는다. 여기서 가장 최악의 경우는, 모든 사람들이 전부 10분이 걸리는 심사관에게 검사를 받아서 최종적으로 60분이 걸리는 경우가 최악일 것이다.

그 이후에는, 아래와 같이 생각을 전개할 수 있다.

이 것을 그대로 코드로 구현하면, 정답을 찾을 수 있다.

⚫️ 정답코드

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var left = 1
    var right = times.max()! * n
    var answer = 0

    while left <= right {
        var peopleCnt = 0
        let mid = (left + right) / 2

        for time in times {
            peopleCnt += mid / time
            if peopleCnt >= n {
                break
            }
        }

        if peopleCnt >= n {
            answer = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return Int64(answer)
}

print(solution(6, [7, 10])) // return 28

 

💬 왜 이 문제는 이분탐색을 이용할까? (파라메트릭 서치?)

정확하게 말하면 이분탐색이 아니다. '파라메트릭 서치'방식을 이용한다.

파라메트릭 서치란 뭘까? 이진탐색과 비슷하듯 다르다. 파라메트릭 서치는, 주어진 일련의 값들이 아니라 주어진 범위내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다. (엥 그래서 이게 이진탐색 아님?)

이진탐색: 1부터 9까지의 '값'중에서 3이라는 값을 찾아내는 과정
파라메트릭 서치: 1부터 9까지의 범위 내에서 3을 찾아내는 과정.

좀 애매하지만, 즉 1부터 9까지 모든 값들을 탐색하면서 3을 찾아내는과정과, 1~9 내부에 3이 있습니까? 를 통해 3을 찾아내는 것을 파라메트릭 서치라고 할 수 있겠다. 이코테 책에서도 나동빈님이 알려주신 것 처럼, '결정문제'로 바꾸어서 풀게 되면 문제 접근이 용이하다. 

특정상황에서 최대/최소값을 문제 (=최적화문제)인 경우, 그냥 그 특정 값이 어떤 조건을 만족하는지만 확인하면 되는 문제 (=결정문제)라고 생각해서 풀어보자.

이 문제에서 에제를 보자. 총 28분의 시간동안, 6명을 처리해야한다. 
28을 7로 나누면 4, 10으로 나누면 2가 되면서 28분동안 총 6명의 사람을 처리할 수 있도록 한다.

처음에 생각하다보니까, 20분에 4번째 사람이 심사가 완료가 되고 10분이 걸리는 심사관 자리가 비어있을 때, 마지막 남은 한 사람은 10분짜리 심사관에게 심사를 받는 경우와, 1분을 더 기다렸다가 21분에 5번째 사람이 나오면 그곳으로 들어가는 방법, 두가지중 선택이 가능하다. 우리가 원하는 '최소'시간을 만족하려면 후자를 선택해야한다.

이렇게 나는 처음에, 순서를 고려해서 생각했기 때문에 곧바로 '이분탐색'이 떠오르지 않았다. 저 갈림길에 대해서 어떻게 선택하게 도와줄 것이냐에 대한 고민이 있었기 떄문이다.

하지만, 정답을 보면 단순히 시간 내부에서 몇명을 처리하는지가 제일 중요하다. 순서는 중요하지 않다. 주어진 시간이 28분이라면 그냥 28분 이내에 6명 처리가 가능한가? 이것만 확인해주면 되는 것이다. 앞에서 말했듯, '우리에게 주어진 시간이 이만큼 (mid만큼) 이라면, 6명이상을 처리할 수 있는가?'라는 결정문제로 접근할 수 있겠다!