오늘 풀어본 문제는 프로그래머스 이분 탐색에 있는 입국 심사이다!
이분 탐색 알고리즘은 거의 풀어 본 적이 없는 것 같았는데, 역시나 접근하기가 어려웠고, 잘못된 방식으로 접근을 하다가 결국 검색을 통해 도움을 받아 해결할 수 있었다,,!
완벽한 나 홀로의 해결이 아니라 아쉽고,, 속상하다 ㅜ
알고리즘을 파바바박 풀어 헤치우고 싶은데,, 쉽지가 않다,,
프로그래머스 입국 심사
소요시간이 각각 다른 입국 심사대가 있고, n 명의 인원을 심사하는데 걸리는 최소 시간을 구하는 문제이다
입출력 및 제한 사항
나의 풀이
이분 탐색 카테고리에 있는 문제 였길래 '이분 탐색을 써야 함 -> 이진 트리를 사용? -> n 명을 이진트리로 구성?' 이라고 아주 단순 무식한 사고 회로를 돌려버렸다..!
지금 생각해보면 n 명으로 이진 트리를 구성하는 것은 참 터무니 없는 생각이다
그저 n명이라는 정보 외에는 그 어떤 조건도, 특징도 없는데 도대체 무얼 가지고 이진 트리고 나발이고를 구성하나..!
또한 이분 탐색 -> 이진 트리? 라는 연상 역시 아쉽다
이분 탐색 : 처음부터 끝까지 모든 것을 확인하지 않고 어떠한 기준으로 절반씩 나누어 탐색해 나가는 과정!!
너무 오랜만이라 그런지 이마저도 까먹었나보다,, ㅜ
문제와 관련된 포스팅을 탐색하다 n 명이 아니라, n명을 심사하는데 걸리는 시간 에 대해서 이분 탐색 을 진행해야 함을 알고 다시 문제를 풀어보았다
해결 풀이
이분탐색을 위해서는 탐색의 범위가 필요하다!
n 명을 심사하기 위해 필요한 시간의 최솟값과 최댓값은 무엇일까?
최솟값은 당연히 1일테고,
최댓값이란 가장 오래걸리는 심사대에서 n명이 모두 심사를 받는 경우일 것이다
그렇다면 문제에서 주어진 예시의 경우
첫 이분 탐색은 [1, 60] 에서 시작하게 된다.
이 구간의 중간값인 30분이 주어진다면 어떨까?
7분이 걸리는 심사대를 A, 10분이 걸리는 심사대를 B라 하면
30분 동안 A 에선 4명이 (30/7), B 에선 3명이 (30/10) 심사를 받게되어 총 7명이 심사가 가능하다
우리는 6명만 심사하면 되기에 다시 작은쪽 범위 [1,29]에서 이분탐색을 시작한다
이런식으로 30분동안 6명을 심사하게되는 시점을 찾아 나간다
이때, 내가 가장 헷갈렸고 이 문제의 핵심이 되는 부분은 6명을 심사할 수 있는 시간 중 최솟값을 구해야 한다는 점이다!
나는 이 부분의 구현에서 좀 애를 먹었고 일부 포스팅을 참고해 완성하였다
먼저 탐색 범위로 잡는 [min, max] 범위에서 min이 max를 추월할 때 까지 탐색 반복문을 실행하고 n명을 심사하게 되는 mid 를 찾을 때 마다 해당 mid 를 임시 정답으로 저장, 더 작은 mid 값을 찾으면 이를 갱신하는 방식으로 코드를 작성하였다
코드
#include <iostream>
#include <vector>
#include <algorithm>
// 프로그래머스 이진 탐색, 입국 심사, level 3
using namespace std;
long long solution(int n, vector<int> times) {
sort(times.begin(), times.end());
unsigned long long left = 1;
unsigned long long right = n*(times[times.size()-1]);
unsigned long long mid;
unsigned long long answer = right;
while (left<=right){ // 최소가 최대를 추월할 때 까지 탐색
unsigned long long count = 0;
mid = (left+right)/2;
// mid 시간 동안 몇명을 검사할 수 있는지 계산 count
for (unsigned long long i = 0; i < times.size(); ++i) {
count += mid/times[i];
}
if (count >= n){
if (mid <= answer){
// 해당 시점의 mid 값을 임시 정답으로 저장, 최소의 mid를 탐색
answer = mid;
}
right = mid-1;
}else {
left = mid+1;
}
}
return answer;
}통과는 하였다만,, 여러모로 찝찝한 문제이다,,
이분 탐색 파트가 자주 나오진 않지만 접근 경험이 확실히 부족한 것 같으니 대비해야겠다..!
