[99클럽/코딩테스트 챌린지/C++] 입국심사 문제에서 이분 탐색과 최적화를 통한 효율적인 풀이

오늘은 이분 탐색을 활용해 입국심사 문제를 풀며 효율적으로 최솟값을 구하는 방법을 배웠습니다. 특히 입력 범위가 매우 클 때 탐색 범위를 줄이고 반복문에서 불필요한 계산을 줄이는 최적화의 중요성을 깨달았습니다.

문제 링크 : 

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

프로그래머스

문제 접근 방법 : 

이 문제는 이분 탐색을 통해 효율적으로 풀 수 있습니다. 이분 탐색을 사용하는 이유는 n명이 심사를 받는 데 걸리는 최소 시간을 찾는 것이며, 특정 시간 내에 n명이 심사를 마칠 수 있는지 확인할 수 있기 때문입니다. 아래는 문제를 해결하는 방법입니다.

 

1. 최소 / 최대 시간 범위 설정 
   • 최소 시간은 모든 심사관이 한 명을 처리하는 최소 시간입니다.
   • 최대 시간은 모든 심사관이 동시에 처리할 때 필요한 최대 시간입니다. 이 값은 가장 느린 심사관이 n 명을 모두 처리하는 데 걸리는 시간이 됩니다.
2. 이분 탐색을 통한 중간 시간 설정 
   • mid 값을 현재 기준 시간으로 설정하고, mid 시간 내에 모든 심사관이 몇 명을 처리할 수 있는 지 계산합니다.
   • mid 시간 내에 처리할 수 있는 사람 수가 n명 이상이라면, mid 값이 최소 시간을 줄일 수 있는 가능성이 있으므로 더 작은 시간도 확인하기 위해 right 값을 줄입니다.
   • 반면, n명 미만이라면 시간이 부족하다는 뜻이므로 left를 mid + 1로 늘려 더 큰 시간을 탐색합니다.
3. 시간 내에 처리할 수 있는 사람 수
   • mid 시간에서 각 심사관이 처리할 수 있는 사람 수는 mid / times[i]로 계산할 수 있습니다.
   • 모든 심사관이 mid 시간내에 처리할 수 있는 총 인원을 합산하고, 이 값이 n 이상인지 검사합니다.
   • 총 인원이 n 이산이면 if (totalPeople >= n) break; 조건을 통해 불필요한 반복을 줄입니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

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

long long wait(long long n,vector<int>& times)
{
    //시간 범위 설정: left는 1, right는 가장 느린 심사관이 모든 사람을 처리할 경우를 가정해
    // times[times.size() - 1] * n으로 설정했습니다.
    long long left = 1, right = times[times.size() - 1] * n;
    long long result = right;
    while(left <= right)
    {
        long long mid = (left + right) / 2;

        long long count = 0;
        for(long long i = 0; i < times.size(); i++)
        {
            //(mid / time)은 해당 시간 동안 각 심사관이 처리할 수 있는 최대 인원을 구하는 공식
            count += mid / times[i];
            if(count >= n) break;
        }

        if(count >= n)
        {
            right = mid - 1;
            result = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return  result;
}


long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());
    return wait(n,times);
}

배운 점과 결론

이 문제를 통해 탐색 범위를 설정하고, 반복문 최적화를 통해 시간을 줄이는 방법의 중요성을 깨달았습니다.

1. 이분 탐색을 통한 효율성 확보
   • 문제에서 최솟값을 찾으라는 조건은 이분 탐색을 활용할 수 있는 신호였습니다. 이분 탐색을 통해 탐색 범위를 절반씩 줄여가며 필요한 시간을 계산함으로써 효율적으로 문제를 해결할 수 있었습니다.
2. 탐색 범위 설정의 중요성
   • left와 right를 설정할 때, left는 최소값인 1, right는 가장 느린 심사관이 모든 사람을 처리할 경우로 설정하여 불필요한 탐색을 줄였습니다. 탐색 범위 설정이 효율적인 풀이로 연결된다는 점을 다시 실감할 수 있었습니다.
3. 반복문 최적화
   • 총 인원 수를 계산할 때, 이미 필요한 인원 수를 넘는 경우 break로 계산을 중단하여 시간을 줄일 수 있었습니다. 필요한 범위 이상의 연산을 줄이는 것이 성능에 크게 영향을 미친다는 것을 확인했습니다.

결론

이번 문제를 통해 이분 탐색과 반복문 최적화가 실질적으로 시간을 얼마나 줄일 수 있는지를 확인할 수 있었습니다. 앞으로 대용량 입력을 다룰 때는 탐색 범위를 최적으로 설정하고, 불필요한 반복을 줄이는 습관을 길러야겠다고 느꼈습니다.