오늘의 학습 키워드

• 대표적인 이분탐색 문제 유형임을 인지하자
• C++의 경우, 연산 중간 과정에서 오버플로우가 발생할 수 있으므로 자료형 선택에 주의가 필요
• 프로그래머스와 같이 입력값의 자료형이 고정된 경우 형변환을 고려하자

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

• [프로그래머스] 입국심사 - 43238
• level 3
• C++ 풀이

문제해설

입국심사를 기다리는 사람 수 n과 각 심사관의 심사 시간 배열 times가 주어졌을 때, 모든 사람이 심사를 받는 데 걸리는 최소 시간을 구하는 문제이다.

접근법: 이분 탐색

문제의 제한사항을 보고 시간복잡도를 신경써야하는 문제임을 인지하고, '이분 탐색으로 접근해볼까?' 라는 생각이 들었다.

제한사항

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

그 다음, 어떤 것을 기준으로 이분 탐색을 해야할지가 관건이다.
심사 받는 사람의 수로 둘까? 아니다. 이 문제는 출력값인 심사 받는 시간을 기준으로 이분 탐색을 진행해야 한다.

• $cnt$: 심사 받는 사람의 누적 수
• $mid$: 이분 탐색의 대상으로, 심사 받는 시간
• $t_i$: $i$번째 심사관이 한 명을 심사하는데 걸리는 시간 ($=times[i]$)

주의사항
이분 탐색은 기본적으로, 값의 범위가 $10^{9}$정도로 크면 int의 최대값에 세이브되어도, 계산 과정에서 오버플로우가 발생할 수 있기 때문에 변수는 long long 타입으로 정의해야 한다는 점은 이미 알고 있을 것이다.
하지만, 프로그래머스와 같이 입력값의 자료형이 고정된 경우, 이 부분을 쉽게 놓칠 수 있다. 실제로, 이 문제에서는 end 값을 구하기 위해 times의 최대값과 n을 곱하게 되는데, 두 값의 자료형이 int이므로 곱셈 과정에서 오버플로우가 발생할 수 있다. 따라서, long long으로 형변환 후 곱해주는 것이 필수다.

end = (long long)*max_element(times.begin(), times.end()) * (long long)n;

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long start = 1, end = (long long)*max_element(times.begin(), times.end()) * (long long)n;
    long long answer = (long long)*max_element(times.begin(), times.end()) * (long long)n;;
    
    while (start <= end){
        long long mid = (start + end) / 2;
        long long cnt = 0;
        for (int t : times){
            cnt += (mid / t);
        }
        if (cnt >= n){
            answer = mid;
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return answer;
}

오늘의 회고

end 계산 과정에서 오버플로우가 발생해 8번 테스트 케이스에서 오류가 발생했다. 처음에는 자료형 문제라고 전혀 인지하지 못하고 프로그래머스에서 제공하는 입력 형태를 그대로 사용했는데, 이 오류를 찾는 데 30분이나 걸렸다. 코딩 테스트에서 발생했다면 정말 아찔한 상황이었을 것이다.
백준과 같은 플랫폼에서는 long long 타입으로 입력을 받을 가능성이 높아 이 문제를 방지할 수 있지만, 프로그래머스처럼 입력 형식이 고정된 경우에는 반드시 형변환에 유의하자.