99클럽 코테 스터디 3일차 TIL + 이진탐색(C++)

문제

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

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

프로그래머스

 

코드

#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long answer = 0;
    long long left = 1;
    long long right = n * (long long)times.back();

    while (left <= right) {
        long long mid = (left + right) / 2;
        long long passed = 0;

        for (int i = 0; i < times.size(); i++) {
            passed += (mid / (long long)times[i]);
        }

        if (passed >= n) {
            answer = mid;
            right = mid - 1;
        } else
            left = mid + 1;
    }

    return answer;
}

ㄴ예제의 테스트 케이스가 매개변수로 주어졌을 때 이진탐색 과정

 

풀이 - 이진 탐색

1. 초기 설정

심사에 필요한 최소 시간을 구하기 위해, left는 최소 시간인 1로, right는 모든 사람이 가장 오래 걸리는 심사관에게 심사를 받을 경우의 최대 시간으로 설정한다. 즉, right = n * times.back()이다.

 

2. 중간 값 계산

mid = (left + right) / 2를 계산하여 해당 시간(mid) 안에 n명을 처리할 수 있는지 확인한다.

 

3. 시간 내 처리 가능한 사람 수 계산

• 각 심사관이 mid 시간 내에 처리할 수 있는 사람 수를 합산하여 passed에 저장한다.
• for (int i = 0; i < times.size(); i++) { passed += (mid / (long long)times[i]); }

 

4. 조건에 따른 탐색 범위 조정

• passed >= n인 경우: mid 시간 내에 n명 이상을 처리할 수 있으므로 가능한 최소 시간을 줄여나가기 위해 answer = mid로 저장하고, right = mid - 1로 right 값을 줄인다.
• passed < n인 경우: mid 시간 내에 n명을 처리할 수 없으므로 시간을 더 늘려야 합니다. 따라서 left = mid + 1로 left를 증가시킨다.

 

이 과정을 통해 심사에 필요한 최소 시간을 answer에 저장하게 되며, 최종적으로 answer를 반환하여 문제를 해결한다.

 

C++에서 타입 캐스팅(형 변환)의 중요성

C++는 다양한 자료형을 지원하는 언어로, 연산 시 두 자료형의 크기가 다를 경우 암묵적 형변환(implicit casting)이 발생할 수 있다. 하지만 이 과정에서 정확한 결과를 얻지 못할 가능성이 생기기 때문에 명시적 형변환(explicit casting)이 중요하게 사용된다.

 

위 코드에서 사용된 타입 캐스팅을 예로 들면,

long long right = n * (long long)times.back() 에서 타입 캐스팅을 하지 않을 시 n과 times.back() 값이 매우 크다면 두 값을 곱할 때 정수 오버플로우가 발생할 수 있다. 즉, int 타입의 범위를 초과하여 예상치 못한 값이 될 수 있다.

마찬가지로 passed += (mid / (long long)times[i]) 에도 타입 캐스팅을 하지 않는다면 연산 과정에서 문제가 발생할 수 있다.

 

이런 경우 명시적으로 피연산자를 long long으로 변환해 주면, 연산 자체가 long long으로 처리되므로 오버플로우를 방지할 수 있다.