[Algorithm] 무지의 먹방 라이브 - 그리디 알고리즘
이 문제의 제목은 무지의 먹방 라이브이다.
상당히 인상깊은 내용이 많아 이렇게 따로 기록하려 한다.
우선 내가 처음에 작성한 코드의 구조를 살펴보자
⬇️ 🖥️ My Code ⬇️
#include <string>
#include <vector>
#include <queue>
using namespace std;
int getZeroCount(vector<int> v) {
int res = 0;
int vSize = v.size();
for(int i=0; i<vSize; i++) {
if(v[i] == 0) res++;
}
return res;
}
int getMin(vector<int> v) {
int min = 1e9;
int vSize = v.size();
for(int i=0; i<vSize; i++) {
if(v[i] < min) min = v[i];
}
return min;
}
int solution(vector<int> food_times, long long k) {
while(getMin(food_times) * (food_times.size() - getZeroCount(food_times)) <= k) {
/*
...
food_times 갱신
k 갱신
...
*/
}
/*
...
*/
return answer;
}
내가 생각하는 이 문제의 핵심은 알맞은 자료구조의 사용이다.
결론부터 말하자면 vector 가 아닌 priority queue 를 사용해야 했다.
그렇다면 priority queue 를 사용하겠다는 발상을 어떻게 하는가?
라는 질문으로 넘어갈 수 있다.
이 문제에서 priority queue 를 사용하게 유도하는 부분은
while 문 안에서 getMin() 을 반복해서 호출한다는 것이다.
우선순위 큐는 <여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진, 일종의 반정렬 상태를 유지> 하는 자료구조이다.
때문에 getMin() 을 vector 에 대하여 반복적으로 호출하는 것보다 priority queue 를 이용하는 게 훨씬 효율적임을 알 수 있다.
이 문제의 정답 코드를 보며 이야기를 계속 하고자 한다.
⬇️ 🖥️ 나동빈 님의 Code ⬇️ (깃헙 주소)
#include <bits/stdc++.h>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int solution(vector<int> food_times, long long k) {
// 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
long long summary = 0;
for (int i = 0; i < food_times.size(); i++) {
summary += food_times[i];
}
if (summary <= k) return -1;
// 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
priority_queue<pair<int, int> > pq;
for (int i = 0; i < food_times.size(); i++) {
// (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
pq.push({-food_times[i], i + 1});
}
summary = 0; // 먹기 위해 사용한 시간
long long previous = 0; // 직전에 다 먹은 음식 시간
long long length = food_times.size(); // 남은 음식의 개수
// summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
while (summary + ((-pq.top().first - previous) * length) <= k) {
int now = -pq.top().first;
pq.pop();
summary += (now - previous) * length;
length -= 1; // 다 먹은 음식 제외
previous = now; // 이전 음식 시간 재설정
}
// 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
vector<pair<int, int> > result;
while (!pq.empty()) {
int food_time = -pq.top().first;
int num = pq.top().second;
pq.pop();
result.push_back({food_time, num});
}
sort(result.begin(), result.end(), compare); // 음식의 번호 기준으로 정렬
return result[(k - summary) % length].second;
}
내가 이 정답코드에서 인상적으로 느낀 4개의 포인트에 대하여 말해보고자 한다.
우선 나동빈 님은,
예외 케이스를 가장 먼저 작성하였다.
solution() 함수 상단을 보면 if (summary <= k) return -1; 이 적혀있는 줄을 볼 수 있다.
문제에서는 분명 <만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.> 고 말했다.
나는 문제를 해결하는 알고리즘을 그대로 이용하여 문제를 풀 수 없음을, 즉 -1을 반환해야 함을 보이려고 했다.
하지만 나동빈님은 문제를 풀 수 없음을 보이는 알고리즘을 따로 분리하여 코드 최상단에 작성하였다.
풀 수 없는 문제에 대하여 가장 빠르게 풀 수 없음을 보이는 알고리즘을 따로 작성했다는 말이다.
이 점이 첫 번째로 인상깊었다.
두 번째로 인상깊은 점은 나동빈님이 주어진 k 를 취급하는 방식이다.
나는 내가 작성한 코드의 solution() 함수 안의 while 문에서 k 값을 갱신해가며 답을 도출하려고 시도했다.
하지만 나동빈님의 코드를 살펴보면,
k 값이 변하지 않음을, immutable 속성을 유지함을 볼 수 있다.
나동빈님은 while 문 안에서 summary length previous 를 갱신한다.
그리고 그 갱신 값의 연산 값과 k 를 비교하는 식으로 while 문의 조건식을 수립한다.
사실 문제에서 주어진 정보 변수를 변화시키는 것이 그렇게 바람직하게 느껴지지 않았다.
앞으로 코드를 작성할 때 이렇게 특정 변수의 immutability 를 유지시키는 방향으로 코드를 작성해야겠다는 생각이 들어 기록한다.
세 번째,
while 문의 조건식과 while 문 안의 수식이 유사한 구조를 갖는다.
코드를 작성하다보면 while 문 안의 코드가 더럽게 마구잡이로 작성될 때가 있다.
하지만 나동빈님의 코드를 보면 while 문의 조건식으로 summary + ((-pq.top().first - previous) * length 이 들어가있다.
또한 while 문 안에는 summary += (now - previous) * length; 의 코드를 볼 수 있다.
조건식과 내부식이 비슷한 구조를 유지하는 것, 깔끔하게 코드를 작성하는 방법임을 기억하고 적용해야겠다.
마지막이다.
마지막은 어떤 착안점으로부터 발상할 수 있는지 아직 잘 파악하지 못했다.
아직까지 그저 창의성, 대단함 등으로 여겨진다.
어떤 부분에서 인상이 깊었냐 하면, 바로
compare 함수를 만들고 priority queue 의 원소들을 vector 에 다시 넣어 compare 의 방식으로 재정렬을 시키는 부분이다.
우선 챙겨갈 수 있는 내용은,
같은 원소를 가진 자료를 이용할 때 서로 다른 두개의 방식으로 각각 정렬하여 이용할 수 있다는 것이다.
pair.first 를 기준으로 내림차순 정렬된 priority queue 를 이용함과 동시에 pair.second 를 기준으로 올림차순 정렬된 vector 또한 이용한다.
뭐, 인상깊었다.
일단은 이렇게 정리한다.
이 문제를 한 줄로 요약하자면
줄 건 주고 다시 생각해보자? 인 것 같다.
priority queue 의 front 에 해당하는 할당량을 애초에 먼저 내어주는 느낌이랄까.
잘 이해하길 바란다.
Leave a comment