문제 : https://programmers.co.kr/learn/courses/30/lessons/43238
서론
혼자 풀어내지 못한 문제.
분류가 이분탐색인데 뭘 이분탐색하라는건지 이해를 못했었다.
그리고 이분의 블로그를 참고하여 이해할 수 있었다.
https://antananarivo.tistory.com/141
원하는 답이 시간이니 시간을 이분탐색 해야한다고 생각할 수도 있었을것 같은데 왜 못했을까 싶다. 시간은 1부터 흘러가야한다는 굳어진 생각을 했었던건 아닌가 싶다.
풀이
시간을 기준으로 이분탐색하여 적합한 시간을 찾아야 한다.
최소시간은 1, times.min, n/times.length 등 다양하게 만들 수 있는데
여기서는 n*times.min/times.length 으로 구현했다.
최소시간 중 가장 커 보이는 값으로, 모든 심사관의 작업 속도가 가장 빠른 심사관과 동일하고 비어있는 심사대가 보이면 곧바로 심사받는 경우의 시간이다.
최대시간은 모든 사람이 가장 느린 심사관 1명에게만 줄서서 심사를 받는 경우로, n * times.max다.
주의할점은 최소시간과 최대시간의 자료형변환이다. 자료형이 int일 경우 제대로된 출력값이 안나온다.
그리고 이분탐색하면서 특정 시간에서 n과 같은 결과가 나오는지 확인한다.
예를들어 예제의 정답인 28분은
1번 심사관이 4명을 처리할 수 있고 ( 28 / 7 = 4 )
2번 심사관이 2명을 처리할 수 있다. ( 28 / 10 = 2 )
즉 28분은 6명을 처리할 수 있으므로 정답이다 ( 6 + 2 )
특정 시간에서 정답보다 많은 인원을 처리할 수 있으면 최대시간을 조정해주고 정답만큼 처리할 수 없으면 최소시간을 조절한다.
그리고 예제1번은
시간이 26에서 5명, 27에서 5명, 28에서 6명, 29에서 6명, 30에서 7명을 처리할 수 있다.
즉 6명을 처리할 수 있는 시간이 28, 29 두가지다.
그렇기에 이분탐색에서 n명이 나왔다고 바로 결과를 출력해선 안되며 n명이 나오는 시간의 최소값을 출력해야한다.
while (start <= end) {
long long num = 0;
mid = (start + end) / 2;
for (int i = 0; i < timesNum; i++) {
num += mid / times[i]; // 현재시간만큼 각 심사관이 처리할 수 있는 모든 인원수를 더한다
}
if (num < n) start = mid + 1;
else {
end = mid - 1;
answer = mid; // n을 만들 수 있는 현재시간 중 최소값을 출력하기 위해 현재시간이 n과 같거나 클때만 결과를 갱신한다.
}
}
디버깅
케이스 8에서 실패가 출력되었다.
원인은 자료형으로,
long long start = (n * times.front()) / timesNum
위 대입연산자의 오른쪽 각 항들이 모두 int형으로 선언되어있었고 계산 결과는 int를 초과했다.
오른쪽 항 중 하나를 long long으로 변경하여 계산결과가 묵시적 형변환이 되도록했다.
수정 전
int timesNum = times.size();수정 후
long long timesNum = times.size();
구현
// c++
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int n, vector<int> times) {
long long answer = 0;
long long timesNum = times.size();
sort(times.begin(), times.end());
long long start = (n * times.front()) / timesNum;
long long end = n * times.back();
long long mid = 0;
while (start <= end) {
long long num = 0;
mid = (start + end) / 2;
for (int i = 0; i < timesNum; i++) {
num += mid / times[i];
}
if (num < n) start = mid + 1;
else {
end = mid - 1;
answer = mid;
}
//cout<<num<<" "<<mid<<endl;
}
return answer;
}
최근댓글