[고득점Kit][이분탐색] 입국심사 ⭐⭐⭐

Date: 2020.11.17 Updated: 2020.11.17

카테고리: Programmers

태그: Binary Search Coding Test Algorithm

[이분탐색] 입국심사

난이도 ⭐⭐⭐

💛 문제

🎀 ‘이분 탐색’ 문제 풀이시 생각해봐야할 것

이분 탐색을 사용하면 모든 경우의 수를 일일이 전부 다 탐색할 필요 없이, 스무고개, 업 다운 게임과 같은 방식으로 답을 찾을 수 있다.

1~100의 범위 中 64를 찾으려 한다면 처음부터 차례 차례 하나씩 검사해가며 찾아야 했을 것이다. 그러나 업 다운 게임 방식으로 생각해본다면 1~100의 중간인 50보다 큰지, 50~100의 중간인 75보다 큰지, 작다면 50~75의 중간인 62보다 큰지 등등 이런식으로 찾아나가면 된다. 범위의 중간 값을 기준으로 비교해 가며 탐색 범위를 절반씩 좁혀나가는 방식을 이진 탐색 알고리즘이라고 한다. 이진 탐색을 사용하여 답을 찾기 위해선 답이 속해있는 범위가 정렬이 되어 있어야 한다! 1~100에서 64를 찾는 일은, 1~100은 그 자체로 순서가 있는, 정렬이 되어 있는 범위이기 때문에 이분 탐색으로 찾는 것이 가능한 것이다. 입력 크기가 굉장히 커서 모든 경우를 순차 탐색하기엔 부담스럽다면, 1️⃣ 구하고자 하는 답이 명확하게 정해져 있고 2️⃣ 구하고자 하는 답의 범위가 정렬이 되어 있다면 이분 탐색으로 답을 찾는 것을 고려해보자! 시간 복잡도는, 즉 mid와 찾고자 하는 답을 비교하는 횟수는 \(O(logN)\) 을 넘지 않는다. 1 ~ 100 에서 64를 찾는 일은 못해도 log100 = 6.xx 6번을 넘지 않는다. 순차 탐색으로 찾으려 했다면 64번을 비교했어야 했을 것이다.

고정 되어 정해져 있는 것은 무엇인지 (비교할 대상이 된다.)
무엇을 이분 탐색으로 찾을 것인가 (mid로 업뎃 해 나갈 것)
찾으려고 하는 것이 속한 범위가 정렬이 되어 있는가

int key = 64; // 찾으려고 하는 답

int start = 1;
int end = 100;

while(start <= end)
{
    int mid = (start + end) / 2;

    if (mid < key)  
        start = mid + 1;
    else if (mid > key)
        end = mid - 1;
    else if (mid == key)
        return mid;
}

return -1;  // start > end 가 되어 빠져나온 경우. 답이 범위에 없는 것임! 

💛 풀이

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

using namespace std;

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

이분 탐색

고정 되어 정해져 있는 것은 무엇인지 (비교할 대상이 된다.)
- n 입국 심사를 기다리는 모든 사람의 수
무엇을 이분 탐색으로 찾을 것인가 (mid로 업뎃 해 나갈 것)
- 모든 사람이 심사를 받는데 걸리는 시간의 최솟값
찾으려고 하는 것이 속한 범위가 정렬이 되어 있는가
- 모든 사람이 심사를 받는데 걸리는 시간의 범위의 최소값은 대충 1 로 상정하고 최대값은 가장 심사가 오래 걸리는 심사관 한명이 모든 사람의 심사를 담당했을 경우의 시간으로 생각해볼 수 있다.
- 예제에서 가장 심사가 오래걸리는 심사관의 심사 시간은 10분이므로, 예제로 따져본다면 모든 사람이 심사를 받는데 걸리는 시간의 범위는 1 ~ 60 (10 * 6) 이 된다. 우리가 찾고자 하는 답인 ‘모든 사람이 심사를 받는데 걸리는 시간’은 이 범위 내에 있다.
- 1 ~ 60 범위는 그 자체로 정렬이 되어 있다. 우리가 찾고자 하는 답인 ‘모든 사람이 심사를 받는데 걸리는 시간’은 이 정렬된 범위 내에 있으므로 이분 탐색을 사용하여 답을 찾을 수 있다.
```
 long long start = 1;
 long long end = (long long)n * *max_element(times.begin(), times.end());
```

모든 경우의 수를 검사하지 않는다. 우리가 찾고자 하는 답인 ‘모든 사람이 심사를 받는데 걸리는 시간’을 업다운 형식으로 범위를 좁혀 나가 찾을 뿐이다. 업 다운의 기준은 정해져 있는 n명을 현재의 시간으로 충분히 커버가 가능한지가 된다. 커버할 수 있는 최소한의 시간을 찾아나가면 된다.

문제에서 명확히 정해져 있는 것은 n 입국 심사를 기다리는 모든 사람의 수.
- n과 비교하여 범위를 업데이트 및 좁혀 나간다.
  - ‘모든 사람이 심사를 받는데 걸리는 시간’을 각각의 입국 심사관의 소요 시간(times 원소들)으로 나눈 값을 다 더하면 👉 현재 범위에서의 mid가 되는 ‘모든 사람이 심사를 받는데 걸리는 시간’을 기준에서의 심사 가능 사람 수 man를 구할 수 있게 된다. 예를 들어 30분 동안엔 30/7 + 30/10 = 총 7 명을 검사할 수 있게 된다.
    mid = (start + end) / 2; long long man = 0; for(auto time : times) man += mid / time;
  - 이를 n과 비교하면 된다.
    - man < n : 이 값이 n보다 작다면 현재의 mid 시간은 너무 적다는 것이다. 이 시간으로는 n명을 심사할 수 없다. 따라서 이 시간보다 더 큰 범위로 좁혀야 한다.
      if (man < n) start = mid + 1;
    - man >= n :
      - 이 값이 n보다 크다면 현재의 mid 시간은 충분하다는 것이다. 최소 시간을 찾아야하므로 혹여나 답이 될 수 있는 가능성도 있다. n보다 더 많은 사람을 심사할 수 있다는 것이니까! 이 시간 보다 더 작은 범위로 좁혀야 한다.
        
        답일 수 도 있다! 그 다음의 mid들이 전부 n명을 커버하기엔 너무 작다면 절대 답이 될 수 없으므로 이 때의 시간이 답이 되기 때문이다. n명을 커버할 수 있는 최소한의 충분한 시간을 구하는 것이기 때문에 이 때 answer에 mid 시간을 업데이트 해놓아야 한다.
      - 이 값이 n과 같다면 현재의 mid 시간은 충분하다는 것이다.
        
        답일 수 도 있다! 그러나 우리가 구하고자 하는 것은 n명을 커버할 수 있는 시간의 최소값이므로 더 작은 시간으로도 n과 일치할 수도 있으니 일단 answer에 mid 시간을 업뎃 해 놓는다.
      - 예를 들어 28분으로 6명을 충분히 커버할 수 있었다면 (28분으로 심사할 수 있는 사람의 수가 6 이상이였다면) 27분도 6명을 커버할 수 있는지 알아봐야 한다. 27분일때는 6명을 커버할 수 없었다면 28분이 답이 된다. 이게 최소값이 될테니까! 실제로도 28명, 29명 둘 다 6명을 처리 할 수 있다. answer는 작거나 같을때마다 업데이트 되므로 최종적으론 최소값인 28이 들어가게 된다.
        else { end = mid - 1; answer = mid; }
answer가 while문에서 한번도 업뎃되지 않을 경우를 대비하여 최대값인 end를 초기값으로 잡는다.
- 한번도 업뎃되지 않았다는건 1 ~ 59 범위의 모든 시간이 n 명을 심사하기엔 전부 부족했다는 것이다.
```
long long answer = end;
```
이 문제는 이분 탐색의 대표 코드에서 mid == answer가 되면 return 되어 빠져나오는 것과 다르게, 정확하게 딱 떨어지는 값을 찾는 것이 아닌 최소값을 찾는 것이기 때문에 answer를 미리 업데이트 해둘 뿐, while을 탈출하는건 start > end 가 될 때 뿐이다.
- mid == answer가 되었다고해서 바로 while문을 빠져나와 answer를 리턴하면 안된다. 답인 28분 말고도 29분일 때 또한 6명을 처리할 수 있었는데 이렇게 했다면 답은 28이 아닌 29로 오답을 리턴했을 것이다. 최소값을 리턴해야 하기 때문에 더 작은 시간에서 6명을 커버할 수는 없는지 또 검사해야 하므로 while문을 빠져나오지 않고 n보다 작거나 클 때마다 계속해서 answer를 업뎃해나가야 한다.

형변환 : long long

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

처음엔 이렇게 코딩을 했었다. 테스트 케이스들이 계속해서 오류가 났었는데 이 문제 때문이였을 줄이야… n과 *max_element(times.begin(), times.end())의 결과는 둘 다 int 자료형이기 때문에 (n * *max_element(times.begin(), times.end())) 이 연산 결과도 당연히 int이다. 그러나 이 연산 결과가 int 형에 담을 수 없을 만큼 큰 값이라면 overflow 가 발생하므로, overflow 되어 부정확해져버린 이 연산 결과로 long long 형변환 해 봤자다.

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

따라서 피연산자 중 하나인 n을 미리 long long으로 형변환 해 두고 n * *max_element(times.begin(), times.end()) 연산을 진행해야 연산 결과가 자동 형변환되어 long long에 올바르게 바로 담기게 된다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️