JArchive 프로그래밍 일기

입국심사 문제 링크 

리뷰 

이분 탐색은 원소들이 정렬된 상태에서 탐색이 가능하므로 sort() 해준다. 

처음에 틀린 부분은, 데이터 타입 때문이다.

이분 탐색의 시작시간과 종료시간 초기화에서 long long 으로 초기화가 안되어 있어서 틀렸다. 

함수의 파라미터 n과 벡터 times는 전부 int 형이다. 

탐색의 최대시간을 초기화할 때, int 벡터의 마지막 인덱스 값을 참조하니까, 따로 (long long)형변환을 해줘야 한다. 

long long solution(int n, vector<int> times) {

  long long max_time = (long long)times[size_of_times-1] * n; // 가장 오래걸리는 시간
}

아래 코드처럼 짜면, max_time변수가  int 곱하기 int 값으로 초기화 된다.

그래서 max_time이 int 형이 된다.  

long long solution(int n, vector<int> times) {

  long long max_time = times[size_of_times-1] * n; // 가장 오래걸리는 시간
}

심사할 사람의 최소값은 1명. 심사 시간 최소값은 1분이다.

따라서 탐색의 최소 시간 min 은 1 이다. 

심사할 사람의 최대값 1,000,000,000명. 심사 시간 최대값은 1,000,000,000분이다. 

심사 시간 최대값 max는 주어진 배열에서 가장 큰 숫자로 초기화 한다.

min,max의 중간값 mid 시간에 n명을 다 처리할 수 있는지 계산한다.

mid 시간 동안 각 심사대는 몇 명을 처리할 수 있는지 계산해서 ( mid_time / times[i] ) man_cnt에 센다.

주어진 시간 안에 man_cnt명을 처리했을 때 n보다 크거나 같아야 한다.

이 때의 mid값이 최소 이면 answer에 저장한다. 

맞은 코드 (테스트케이스 10개 중 10개 O)

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

long long solution(int n, vector<int> times) {

  int size_of_times = times.size();
  sort(times.begin(), times.end());

  long long min_time = 1L; // 가장 짧은 시간
  long long max_time = (long long)times[size_of_times-1] * n; // 가장 오래걸리는 시간
  long long mid_time = (min_time + max_time) / 2; // 중앙값
  long long answer = max_time;

  while(min_time <= max_time){

    mid_time = (min_time + max_time) / 2;
    long long man_cnt = 0;
    for(auto t : times) { // mid_time 동안 처리할 수 있는 사람 수를 센다.
      man_cnt += mid_time / t;
    }

    if(n <= man_cnt){
      answer = min(answer, mid_time);
      max_time = mid_time - 1;
    }
    else {
      min_time = mid_time + 1; // 시간이 부족
    }
  }
  return answer;
}

틀린 코드  (테스트케이스 10개 중 9개 O)

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

long long solution(int n, vector<int> times) {

  int size_of_times = times.size();
  sort(times.begin(), times.end());

  long long min_time = 1L; // 가장 짧은 시간
  long long max_time = times[size_of_times-1] * n; // 가장 오래걸리는 시간
  long long mid_time = (min_time + max_time) / 2; // 중앙값
  long long answer = max_time;

  while(min_time <= max_time){

    mid_time = (min_time + max_time) / 2;
    long long man_cnt = 0;
    for(auto t : times) { // mid_time 동안 처리할 수 있는 사람 수를 센다.
      man_cnt += mid_time / t;
    }

    if(n <= man_cnt){
      answer = min(answer, mid_time);
      max_time = mid_time - 1;
    }
    else {
      min_time = mid_time + 1; // 시간이 부족
    }
  }
  return answer;
}