문제
접근 방식
플러그를 최소한으로 빼면서 전기용품을 사용하려면
이후에 다시 쓰일 전기용품의 플러그를 빼는 것보단
나중에 쓰일 일이 없는 플러그를 빼는 것이 효율적일 것이고
만약 나중에 쓰인다면 가장 나중에 쓰이는 것을 빼는 게 효율적이다.
아래와 같이 상황을 세 가지로 나누어 처리해 주면 된다.
- 이미 멀티탭에 꽂힌 전기용품이면 그대로 사용하면 되니 아무런 행동도 하지 않음
- 멀티탭에 빈 공간이 있는 경우에는 그대로 빈 공간에 꽂음
- 빈 공간이 없으면 앞으로 사용되지 않거나 가장 나중에 사용되는 것을 빼고 새로 꽂음
첫 번째 상황을 처리하기 위해 불리언 배열을 만들어
멀티탭에 꽂거나 뺄 때마다 상태를 바꿔주었고
두 번째와 세 번째 상황을 처리하기 위해 정수형 배열을 만들어
멀티탭에 꽂혀 있는 플러그들이 어떤 것인지 알 수 있게 저장했다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] history = new int[k + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= k; i++) {
history[i] = Integer.parseInt(st.nextToken());
}
int tab = n;
int[] arr = new int[n];
boolean[] isUsed = new boolean[k + 1];
int count = 0;
for (int i = 1; i <= k; i++) {
int target = history[i];
int idx = 0;
int late = 0;
if (isUsed[target]) continue;
if (tab > 0) {
tab--;
for (int j = 0; j < n; j++) {
if (arr[j] == 0) {
arr[j] = target;
break;
}
}
isUsed[target] = true;
continue;
}
count++;
for (int j = 0; j < n; j++) {
int use = arr[j];
int x = 0;
for (int l = i + 1; l <= k; l++) {
if (history[l] == use) {
x = l;
break;
}
}
if (x == 0) {
idx = j;
break;
}
if (x > late) {
late = x;
idx = j;
}
}
tab--;
isUsed[arr[idx]] = false;
isUsed[target] = true;
arr[idx] = target;
}
System.out.println(count);
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 11286번 : 절댓값 힙 (1) | 2024.01.21 |
---|---|
[백준] 18808번 : 스티커 붙이기 (0) | 2024.01.19 |
[백준] 1744번 : 수 묶기 (0) | 2024.01.11 |
[백준] 2170번 : 선 긋기 (1) | 2024.01.11 |
[백준] 2457번 : 공주님의 정원 (0) | 2024.01.10 |