Programmers - 이분 탐색
이분탐색을 코드로 옮기는데 오래걸렸다. 세부적인 부분에 실수를 많이 했다.(mid - 1, mid +1, small<=big 같은것) 연습이 필요하다.
나의 풀이
특정 조건을 만족하는 값을 찾기 위한 이분탐색 문제다. 어떤원소가 상한값을 넘는지 알 수 없기에 순환하며 총 합을 구하기위해 big-O=n 의 탐색을 사용했다. 여기서 시간이 많이 소요됬다.
int solution(vector<int> budgets, int M) {
int answer = 0;
sort(budgets.begin(), budgets.end(), greater<int>());
int small = 0, big = budgets.front();
int m, maxbud;
maxbud = (big + small) / 2;
while (small <= big)
{
m = M;
for (int b : budgets)
{
if (m < 0)
{
break;
}
m -= (b > maxbud) ? maxbud : b;
}
if (m < 0)
{
big = maxbud - 1;
}
else
{
small = maxbud + 1;
}
maxbud = ((big + small) / 2.0);
}
answer = maxbud;
return answer;
}
다른 사람 풀이(똑똑한 풀이)
오름차순으로 정렬된 예산을 순회하며 상한값을 남은 예산과 남은 숫자로 나눈 값으로 하며 이를 초과하는 예산이 나오면 반환하여 상한값을 계산하였다.
int solution2(vector<int> budgets, int M) {
int answer = 0;
int numbers = budgets.size();
sort(budgets.begin(), budgets.end());
for (int b : budgets)
{
if (b > (M / numbers))
{
return M / numbers;
}
else
{
M -= b;
numbers--;
}
}
return budgets.back();
}
나의 풀이
가장 작은 누적합의 심사관부터 사용하여 목표 사람의 수만큼 누적합을 계산하여 모든 사람이 심사를 받는 최솟값을 구했다. 하지만 입국심사를 기다리는 사람이 1 ~ 1000000000명이라서 시간을 초과하게 되었다.
long long solution2(int n, vector<int> times) {
long long answer = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int t : times)
{
pq.push(make_pair(t, t));
}
int cnt = 1;
while (cnt != n)
{
pq.push(make_pair(pq.top().first + pq.top().second, pq.top().second));
pq.pop();
cnt++;
}
return pq.top().first;
}
다른 사람 풀이
걸리는 시간 동안 최대한 심사를 받을 수 있는 사람의 수를 이분탐색하여 사람의 수와 목표한 n과 일치하는 최소의 시간이 답이 된다.
int solution4(int n, vector<int> times) {
long long start = 1, end = 0;
for (int t : times)
{
if (end < t)
end = t;
}
end *= n;
while (start < end)
{
long long mid = (start + end) / 2;
long long p = 0;
for (int t : times)
{
p += mid / t;
}
if (p < n)
{
start = mid + 1;
}
else
{
end = mid;
}
}
return start;
}
나의 풀이
처음에는 가장 작은 간격을 찾고 해당 간격과 접한 2개의 간격 중 작은 간격을 우선적으로 제거하였다. 하지만 오류가 있다.
int solution2(int distance, vector<int> rocks, int n) {
constexpr int BIGINT = numeric_limits<int>::max();
sort(rocks.begin(), rocks.end());
rocks.push_back(distance);
list<int> r;
r.push_back(rocks[0]);
for (int i = 1; i < rocks.size(); i++)
{
r.push_back(rocks[i] - rocks[i - 1]);
}
list<int>::iterator small, left, right;
int smallVal;
while (n)
{
smallVal = BIGINT;
for (auto i = r.begin(); i != r.end(); i++)
{
if (smallVal > * i)
{
small = i;
smallVal = *i;
}
}
left = right = small;
int lVal, rVal;
if (left != r.begin())
{
left--;
lVal = *left;
}
else
lVal = BIGINT;
right++;
if (right != r.end())
{
rVal = *right;
}
else
rVal = BIGINT;
if (rVal < lVal)
{
r.erase(right);
*small = rVal + smallVal;
}
else
{
r.erase(left);
*small = lVal + smallVal;
}
n--;
}
smallVal = BIGINT;
for (int a : r)
{
if (a < smallVal)
smallVal = a;
}
return smallVal;
}
다른사람 풀이
일정 간격 이하의 돌을 전부 제거하며 제거의 가능성 여부를 판단하며 이분탐색하여 답을 찾는다.
#include <vector>
#include <algorithm>
using namespace std;
int solution(int d, vector<int> rocks, int n) {
int l=0, r=d;
sort(rocks.begin(), rocks.end());
rocks.push_back(d);
while(l<r) {
int m=(l+r)/2, p=0, k=0;
for(int i : rocks)
if(i-p<=m)
k++;
else
p=i;
if(k<=n) l=m+1;
else r=m;
}
return r;
}
댓글남기기