이 문서에서는 NordicOI 2023 대회의 "Ice Cream Machines" 문제를 풀어봅니다. 핵심은 그리디 알고리즘(greedy algorithm)과 우선순위 큐(priority queue)를 활용하여 기계 청소 횟수를 최소화하는 것입니다.
문제 요약
아이스크림 가게에 N명의 손님이 줄을 서 있습니다. 가게에는 M가지의 아이스크림 맛이 있고, K대의 아이스크림 제조 기계가 있습니다. 각 손님은 자신이 원하는 특정 맛의 아이스크림을 주문합니다. 각 기계는 한 번에 한 가지 맛의 아이스크림만 만들 수 있으며, 다른 맛을 만들려면 기계를 청소해야 합니다. 초기에는 모든 기계가 비어 있어 첫 사용 시 청소가 필요합니다. 우리의 목표는 전체 손님을 처리하는 동안 기계 청소 횟수를 최소화하는 것입니다.
핵심 아이디어
이 문제는 페이지 교체(page replacement) 알고리즘의 변형으로 볼 수 있습니다. 기계를 캐시(cache) 슬롯으로, 아이스크림 맛을 페이지(page)로 생각할 수 있습니다. 가장 효율적인 전략은 가장 나중에 다시 사용될 맛을 교체하는 것입니다. 즉, Belady의 최적 알고리즘(Belady's optimal algorithm)과 유사한 접근법입니다.
구체적인 알고리즘은 다음과 같습니다:
- 각 아이스크림 맛별로 손님들의 등장 순서를 큐(queue)에 저장합니다.
- 각 기계가 현재 담당하는 맛과 그 맛이 다음에 등장할 순서를 추적합니다.
- 손님을 순서대로 처리하면서:
- 현재 손님이 원하는 맛이 이미 어떤 기계에 있다면, 해당 기계의 다음 등장 순서 정보를 갱신합니다.
- 원하는 맛이 어느 기계에도 없다면, 청소 횟수를 1 증가시키고, 가장 나중에 다시 필요할 맛을 담당하는 기계를 교체합니다. 만약 어떤 기계가 다시 사용되지 않을 맛을 담당한다면, 그 기계를 우선적으로 교체합니다.
코드 구현 (C++)
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>
using namespace std;
class Solution {
public:
int solve(int numFlavors, int numMachines, vector<int>& requests) {
int numCustomers = requests.size();
// 각 맛별 손님 등장 순서 큐 (1-based index)
vector<queue<int>> flavorQueues(numFlavors + 1);
for (int i = 0; i < numCustomers; ++i) {
flavorQueues[requests[i]].push(i);
}
// 각 맛이 현재 어떤 기계에 할당되어 있는지 저장 (-1: 할당 안 됨)
vector<int> flavorToMachine(numFlavors + 1, -1);
// {다음 등장 순서, 맛} 쌍을 저장하는 멀티셋
multiset<pair<int, int>> nextAppearance;
// 초기화: 모든 기계는 비어 있음 (다음 등장 순서를 아주 큰 값으로 설정)
for (int i = 0; i < numMachines; ++i) {
nextAppearance.insert({numCustomers + 1, numFlavors + 1});
}
int cleaningCount = 0;
for (int i = 0; i < numCustomers; ++i) {
int currentFlavor = requests[i];
// 현재 맛의 다음 등장 순서 계산
int nextTime = numCustomers + 1;
if (!flavorQueues[currentFlavor].empty()) {
nextTime = flavorQueues[currentFlavor].front();
}
if (flavorToMachine[currentFlavor] != -1) {
// 현재 맛이 이미 기계에 있음 -> 기존 정보 갱신
auto it = nextAppearance.find({flavorToMachine[currentFlavor], currentFlavor});
if (it != nextAppearance.end()) {
nextAppearance.erase(it);
}
// 다음 등장 순서 업데이트
flavorToMachine[currentFlavor] = nextTime;
nextAppearance.insert({nextTime, currentFlavor});
} else {
// 새로운 맛 -> 기계 청소 필요
cleaningCount++;
// 가장 나중에 다시 사용될 맛을 가진 기계 찾기
auto lastIt = prev(nextAppearance.end());
int lastTime = lastIt->first;
int lastFlavor = lastIt->second;
nextAppearance.erase(lastIt);
// 기존 맛 제거
if (lastFlavor <= numFlavors) {
flavorToMachine[lastFlavor] = -1;
}
// 현재 맛 할당
flavorToMachine[currentFlavor] = nextTime;
nextAppearance.insert({nextTime, currentFlavor});
}
// 현재 손님 처리 완료 -> 큐에서 제거
if (!flavorQueues[currentFlavor].empty()) {
flavorQueues[currentFlavor].pop();
}
}
return cleaningCount;
}
};
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<int> c(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &c[i]);
}
Solution sol;
printf("%d\n", sol.solve(m, k, c));
return 0;
}알고리즘 설명
flavorQueues: 각 맛별로 손님들이 등장하는 순서(인덱스)를 저장하는 큐의 배열입니다.flavorToMachine: 각 맛이 할당된 기계의 상태를 저장합니다. 실제로는 다음 등장 순서를 저장하는 데 사용됩니다.-1은 할당되지 않음을 의미합니다.nextAppearance: 각 기계(사실은 기계에 할당된 맛)가 다음에 등장할 순서를 저장하는multiset입니다.{다음_등장_순서, 맛}형태로 저장되며, 자동으로 정렬됩니다. 가장 마지막 원소가 가장 나중에 다시 등장하는 맛입니다.
알고리즘의 핵심은 새로운 맛이 요청되었을 때, 현재 기계에 있는 맛들 중에서 가장 나중에 다시 필요해질 맛을 교체하는 것입니다. 이는 전체 청소 횟수를 최소화하는 최적의 전략입니다. multiset을 사용하면 마지막 원소를 O(log K) 시간에 찾고 제거할 수 있습니다.
시간 복잡도
각 손님을 처리할 때 multiset에 대한 삽입/삭제 연산이 발생하므로, 전체 시간 복잡도는 O(N log K)입니다. 여기서 N은 손님 수, K는 기계 수입니다. 메모리 복잡도는 O(N + M + K)입니다.
예제 테스트
주어진 예제를 통해 알고리즘을 검증할 수 있습니다.
예제 1
입력:
8 3 1
2
3
3
1
2
1
1
3
출력: 6예제 2
입력:
8 3 2
2
3
3
1
2
1
1
3
출력: 4