백준 - 멀티탭 스케줄링 (1700) : JAVA
문제 유형
그리디
풀이 방법 도출
문제의 조건은 다음과 같습니다.
1. 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.
2. 첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.
3. 하나씩 플러그를 빼는 최소의 횟수를 출력하시오.먼저 주어진 조건을 통해서 어떻게 풀어나가야할지 고민했습니다.
"N과 K가 최대 100이다."
-> 위 조건을 통해 2차, 3차 반복문까지도 허용될 수 있다는 점을 감안합니다. 1차 반복문으로 해결할 수 있다면, 굳이 100으로 상한을 줬을 이유가 없습니다.
"전기 용품의 이름이 K이하의 자연수이다."
전기 용품의 이름이 예를 들어서 최대 10억일 수도 있는데 K이하의 자연수로 제한했다는 것은, 배열의 인덱스를 사용할 수 있는 힌트라고 생각할 수 있습니다.
이러한 힌트들을 얻고 매번 어떻게 최적의 선택을 할 수 있을 지를 고민합니다.
현재 문제에서는 미래의 선택을 알고 있기 때문에 미리의 선택을 고려해서 현재 최적의 선택을 할 수 있습니다.
2 7
2 3 2 3 1 2 7문제 테스트케이스에서 플러그를 뽑아야하는 순간은 1을 꼽아야할때입니다.
이 때 2와 3중 어느 플러그를 뽑아야할지는 매우 자명합니다.
-> 이후 스케줄링에 2는 등장하고 3은 등장하지 않기 때문에 3을 제거합니다.
여기서 더 생각해봐야하는 것은 미래의 선택에 "2와 3이 모두 등장할 때는?"
-> 이 경우에는 2와 3 중 어떤 전기용품이 먼저 등장했는지에 따라서 제거할 것을 선택합니다.
이를 구현한 핵심 코드는 다음과 같습니다.
int cnt = 0;
int answer = 0;
for (int i = 0; i < k; i++) {
int cur = seq[i];
if (vis[cur]) continue;
if (cnt < n) {
vis[cur] = true;
cnt++;
} else {
int[] arr = new int[k + 1];
int weight = k + 1;
for (int j = i + 1; j < k; j++) {
arr[seq[j]] = Math.max(arr[seq[j]], weight--);
}
List < Node > list = new ArrayList < > ();
for (int j = 1; j <= k; j++) {
if (vis[j]) list.add(new Node(j, arr[j]));
}
list.sort((n1, n2) - > n1.value - n2.value);
vis[list.get(0).num] = false;
answer++;
vis[cur] = true;
}
}멀티탭 사용 횟수(cnt)가 n이고 사용하려는 전기용품이 꼽아져있지 않다면, 미래의 선택에 따라 가중치를 부여한 후에, 가중치가 가장 낮은 전기용품을 제거합니다.
주의해야할 점은 미래의 선택이 "2 3 2"일 경우를 고려해서 Math.max를 통해 높은 가중치를 유지하도록 합니다.
시간 복잡도
O(K * K log K)
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Node {
int num;
int value;
Node (int num, int value) {
this.num = num;
this.value = value;
}
}
public class Main {
static int n, k;
static boolean[] vis;
static int[] seq;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
vis = new boolean[k+1];
seq = new int[k];
st = new StringTokenizer(br.readLine());
for (int i=0; i<k; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
int answer = 0;
for (int i=0; i<k; i++) {
int cur = seq[i];
if (vis[cur]) continue;
if (cnt < n) {
vis[cur] = true;
cnt++;
}
else {
int[] arr = new int[k+1];
int weight = k+1;
for (int j=i+1; j<k; j++) {
arr[seq[j]] = Math.max(arr[seq[j]], weight--);
}
List<Node> list = new ArrayList<>();
for (int j=1; j<=k; j++) {
if (vis[j]) list.add(new Node(j, arr[j]));
}
list.sort((n1,n2)-> n1.value - n2.value);
vis[list.get(0).num] = false;
answer++;
vis[cur] = true;
}
}
System.out.println(answer);
}
}
