[Programmers_C++]#Level3_입국 심사, 이분 탐색

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 이분 탐색

[알고리즘]#1_이분 탐색(Binary Search)

 

• [정의] : 이분 탐색은 정렬된 데이터 목록에서 특정 값을 찾는 데 사용되는 탐색 알고리즘입니다.
• [특징] : 데이터 목록이 정렬된 상태일 때, 활용 가능한 알고리즘입니다.
• [동작 방식]
  1. 배열의 시작 지점을 가리키는 포인터, 배열의 마지막 지점을 가리키는 포인터, 두 개의 포인터 초기화
  2. 두 개의 포인터가 지정하는 부분 배열의 중간 위치를 구합니다.
  3. 중간 위치의 값이 목표 값보다 작다면, 오른쪽 경계를 중간 위치-1 위치로 변경
  4. 중간 위치의 값이 목표 값보다 크다면, 왼쪽 경계를 중간 위치+1 위치로 변경
  5. 목푯 값을 찾을 때까지, 2~4번 동작을 반복합니다.

 

2. 평균 시간 동안 몇 명?

1. 먼저, 심사관들을 심사에 걸리는 시간 기준 오름차순 정렬합니다.
2. 심사에 걸리는 최소 시간을 1로, 최대 시간을 심사 인원 중 제일 오래 걸리는 심사 시간에 n을 곱한 시간
3. 그리고, 평균 시간을 (최소 시간 + 최대 시간)/2로 설정하고, 이 시간 동안 심사관들이 심사할 수 있는 사람 수
4. 심사 가능한 사람 수가 주어진 n보다 크거나 같을 경우, 최소 심사 시간을 갱신하고, 최대 시간을 midTime-1로 설정
5. 심사 가능한 사람 수가 주어진 n보다 작을 경우, 최소 시간을 midTime+1로 갱신합니다.
6. 3~5번 과정을 반복하며, 최종적으로 총 최소 심사 시간을 구합니다.

 

---

 

#3. 코드

 

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

using namespace std;

/*

    0. 이분 탐색 활용을 위해 tiems를 오름차순 정렬
    1. 최소 시간 = 1, 최대 시간 = n * times의 마지막 원소

    2. while 문 순회하며 중간 시간 구하기.
    3. 중간 시간 동안 times의 각 심사 인원이 심사할 수 있는 최대 인원 총합 구하기
    4. 위에서 구한 총 합이 주어진 n보다 크거나 같을 경우, 결과 값을 업데이트하고 maxTime = minTime-1로 설정
    5. 위에서 구한 총 합이 주어진 n보다 작을 경우, minTime = midTime+1로 설정
    6. 2 ~ 5번 작업 반복, 데이터 유형 주의
*/

long long solution(int n, vector<int> times)
{
    long long answer = 0;

    // #1. 오름차순 정렬
    sort(begin(times), end(times));

    // #2. n을 심사하는데 걸리는 최소 시간, 최대 시간
    long long minTime = 1;
    long long maxTime = n * (long long)times[(int)times.size() - 1];
    answer = maxTime;

    // #3. 이분 탐색
    while (minTime <= maxTime)
    {
        // #3-1. 중간 시간 구하기
        long long midTime = (maxTime + minTime) / 2;
        long long people = 0;

        // #3-2. 중간 시간 동안 심사 인원들이 심사할 수 있는 최대 인원 총합 구하기
        for (int i = 0; i < (int)times.size(); ++i)
        {
            people += midTime / times[i];
        }

        // #3-3. 중간 시간 동안 심사할 수 있는 인원의 총합과 주어진 n을 비교
        // #1. 총합이 n과 같거나 클 경우, 정답을 minTime으로 업데이트하고 maxTime = midTime-1로 갱신
        if (people >= n)
        {
            if (answer > midTime)
            {
                answer = midTime;
            }
            maxTime = midTime - 1;
        }
        // #2. 총합이 n보다 작을 경우, minTime = midTime+1로 갱신
        else
        {
            minTime = midTime + 1;
        }
    }

    return answer;
}

 

---