이번에는 백준 1700번 멀티탭 스케줄링 문제를 풀어보았습니다.
멀티탭의 구멍 수보다 많은 전기용품을 순서대로 사용해야 하며, 새로운 전기용품을 꽂기 위해 기존 플러그를 빼야 할 때 그 횟수를 최소화해야 합니다.
현재 꽂혀 있는 전기용품 중에서 앞으로 다시 사용되지 않거나, 가장 늦게 다시 사용되는 전기용품을 제거하는 그리디 방식으로 해결하였습니다.
문제 설명
멀티탭의 구멍 개수 N과 전기용품 사용 횟수 K가 주어집니다.
이후 전기용품의 사용 순서가 주어졌을 때, 모든 전기용품을 순서대로 사용하기 위해 플러그를 뽑아야 하는 최소 횟수를 구하는 문제입니다.
이미 멀티탭에 꽂혀 있는 전기용품을 다시 사용하는 경우에는 아무 작업도 하지 않아도 됩니다.
하지만 멀티탭이 가득 찬 상태에서 새로운 전기용품을 사용해야 한다면, 기존 전기용품 중 하나를 빼야 합니다.
풀이 아이디어
현재 멀티탭이 가득 찬 상태에서 새로운 전기용품을 꽂아야 한다면, 어떤 전기용품을 제거해야 하는지를 결정해야 합니다.
이때 다음 기준을 사용하였습니다.
- 앞으로 다시 사용되지 않는 전기용품이 있다면 해당 전기용품을 제거합니다.
- 모두 다시 사용된다면, 다음 사용 시점이 가장 늦은 전기용품을 제거합니다.
앞으로 다시 사용되지 않는 전기용품은 지금 제거해도 이후에 다시 꽂을 필요가 없습니다.
또한 모두 다시 사용된다면, 가장 늦게 사용되는 전기용품을 제거해야 그동안 다른 전기용품을 최대한 오래 유지할 수 있습니다.
각 전기용품의 다음 사용 시점을 빠르게 확인하기 위해
vector<queue<int>> q_vector;를 사용하였습니다.
각 큐에는 해당 전기용품이 사용되는 인덱스를 순서대로 저장하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<queue<int>> q_vector;
vector<int> inp;
bool connected[101];
int connected_cnt;
int N,K;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
cin >> K;
q_vector.resize(K+1,queue<int>());
for (int i=0; i<K; i++) {
int temp;
cin >> temp;
inp.push_back(temp);
q_vector[temp].push(i);
}
int ret = 0;
for (int i=0; i<K; i++) {
q_vector[inp[i]].pop();
if (connected_cnt == N) {
if (connected[inp[i]]) continue;
else {
int max_val = 0;
int max_index = K+1;
for (int j=1; j<K+1; j++) {
if (connected[j] && q_vector[j].empty()) {
max_index = j;
break;
} else if (connected[j] && q_vector[j].size()) {
if (max_val < q_vector[j].front()) {
max_val = q_vector[j].front();
max_index = j;
}
}
}
ret++;
connected[max_index] = false;
connected[inp[i]] = true;
}
} else {
if (connected[inp[i]]) continue;
else {
connected_cnt++;
connected[inp[i]] = true;
}
}
}
cout << ret;
return 0;
}풀이 흐름
-
각 전기용품이 사용되는 모든 시점을 큐에 저장합니다.
-
전기용품의 사용 순서를 처음부터 탐색합니다.
-
현재 사용 시점은 이미 처리한 것이므로 해당 전기용품의 큐에서 현재 인덱스를 제거합니다.
-
현재 전기용품이 이미 멀티탭에 꽂혀 있다면 다음 순서로 넘어갑니다.
-
멀티탭에 빈자리가 있다면 현재 전기용품을 꽂고 연결 개수를 증가시킵니다.
-
멀티탭이 가득 찼다면 현재 연결된 전기용품들의 다음 사용 시점을 확인합니다.
-
앞으로 다시 사용되지 않는 전기용품이 있으면 해당 전기용품을 제거합니다.
-
모든 전기용품이 다시 사용된다면 다음 사용 시점이 가장 늦은 전기용품을 제거합니다.
-
제거 횟수를 증가시키고 현재 전기용품을 멀티탭에 연결합니다.
구현 포인트
1. 전기용품별 사용 시점 저장
vector<queue<int>> q_vector;각 전기용품 번호에 대응하는 큐를 만들었습니다.
입력받은 전기용품의 사용 순서를 순회하면서 해당 전기용품이 사용되는 인덱스를 큐에 저장합니다.
for (int i=0; i<K; i++) {
int temp;
cin >> temp;
inp.push_back(temp);
q_vector[temp].push(i);
}예를 들어 전기용품 2가 1, 4, 7번째에 사용된다면 다음과 같이 저장됩니다.
q_vector[2] = {1, 4, 7}이를 통해 각 전기용품이 다음에 언제 사용되는지 빠르게 확인할 수 있습니다.
2. 현재 사용 시점 제거
q_vector[inp[i]].pop();현재 i번째 전기용품을 사용하기 직전에, 해당 전기용품의 큐에서 현재 사용 시점을 제거합니다.
따라서 이 작업 이후 큐의 맨 앞에는 현재 시점 이후의 가장 가까운 사용 시점이 남게 됩니다.
큐가 비어 있다면 해당 전기용품은 앞으로 다시 사용되지 않는다는 의미입니다.
3. 현재 연결 상태 관리
bool connected[101];
int connected_cnt;connected[x]는 전기용품 x가 현재 멀티탭에 꽂혀 있는지를 나타냅니다.
connected[x] == true라면 이미 연결된 상태이고,
connected[x] == false라면 연결되지 않은 상태입니다.
connected_cnt는 현재 멀티탭에 연결된 전기용품의 개수를 저장합니다.
4. 멀티탭에 빈자리가 있는 경우
if (connected_cnt != N)멀티탭에 빈자리가 있고 현재 전기용품이 이미 연결되어 있다면 아무 작업도 하지 않습니다.
if (connected[inp[i]]) continue;현재 전기용품이 연결되어 있지 않다면 빈자리에 꽂습니다.
connected_cnt++;
connected[inp[i]] = true;이 경우에는 기존 플러그를 뽑지 않으므로 ret은 증가하지 않습니다.
5. 멀티탭이 가득 찬 경우
if (connected_cnt == N)멀티탭이 가득 찼더라도 현재 전기용품이 이미 연결되어 있다면 플러그를 교체할 필요가 없습니다.
if (connected[inp[i]]) continue;현재 전기용품이 연결되어 있지 않을 때만 기존 전기용품 하나를 제거해야 합니다.
6. 앞으로 사용되지 않는 전기용품 제거
if (connected[j] && q_vector[j].empty()) {
max_index = j;
break;
}현재 연결된 전기용품 중 큐가 비어 있는 전기용품은 앞으로 다시 사용되지 않습니다.
이러한 전기용품은 지금 제거하더라도 이후에 다시 연결할 필요가 없으므로 가장 우선적으로 제거할 수 있습니다.
하나를 찾는 즉시 제거 대상으로 결정하고 반복문을 종료합니다.
7. 가장 늦게 다시 사용되는 전기용품 제거
앞으로 다시 사용되지 않는 전기용품이 없다면 모든 전기용품의 다음 사용 시점을 비교합니다.
else if (connected[j] && q_vector[j].size()) {
if (max_val < q_vector[j].front()) {
max_val = q_vector[j].front();
max_index = j;
}
}q_vector[j].front()는 전기용품 j가 다음에 사용되는 인덱스입니다.
이 값이 가장 큰 전기용품을 선택하면 가장 늦게 다시 사용되는 전기용품을 제거하게 됩니다.
가장 늦게 사용할 전기용품을 제거하면 그전까지 다른 전기용품들을 계속 사용할 수 있으므로 플러그 교체 횟수를 최소화할 수 있습니다.
8. 플러그 교체
제거할 전기용품을 결정했다면 다음과 같이 상태를 변경합니다.
ret++;
connected[max_index] = false;
connected[inp[i]] = true;기존 플러그를 하나 뽑았으므로 ret을 증가시킵니다.
이후 제거 대상으로 선택한 전기용품을 연결 해제하고, 현재 사용할 전기용품을 연결합니다.
기존 전기용품 하나를 빼고 새로운 전기용품 하나를 연결한 것이므로 connected_cnt는 변하지 않습니다.
9. 그리디 선택이 가능한 이유
멀티탭이 가득 찬 상태에서 새로운 전기용품을 연결해야 할 때, 현재 연결된 전기용품 중 하나는 반드시 제거해야 합니다.
앞으로 다시 사용되지 않는 전기용품을 제거하면 이후에 해당 전기용품을 다시 꽂을 일이 없으므로 가장 유리합니다.
모든 전기용품이 다시 사용된다면 가장 늦게 다시 사용되는 전기용품을 제거합니다.
가까운 미래에 사용할 전기용품을 제거하면 곧 다시 꽂아야 하므로 추가 교체가 발생할 가능성이 높습니다.
따라서 다음 사용 시점이 가장 늦은 전기용품을 제거하는 것이 최적의 선택이 됩니다.
10. 시간복잡도
입력된 전기용품의 사용 순서를 K번 탐색합니다.
멀티탭이 가득 찬 상태에서 교체가 필요할 때마다 최대 K개의 전기용품을 확인합니다.
따라서 전체 시간복잡도는
O(K²)입니다.
문제에서 K는 최대 100이므로 충분히 통과할 수 있습니다.
