728x90
백준 1700 - 멀티탭 스케줄링
https://www.acmicpc.net/problem/1700

문제
ex. 3구 멀티탭 사용 순서
키보드 -> 헤어드라이기 -> 핸드폰 충전기 -> 디지털 카메라 충전기 -> 키보드 -> 헤어드라이기
=> 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음
디지털 카메라 충전기 플러그를 꽂기 전 핸드폰 충전기 플러그를 빼는 것이 최적 -> 1번만 빼면 됨
입력
첫 줄: 멀티탭 구멍의 개수 N (1 <= N <= 100), 전기 용품의 총 사용횟수 K (1 <= K <= 100)
두 번째 줄: 전기용품의 이름 <= K
출력: 하나씩 플러그를 빼는 최소의 횟수
풀이
가장 나중에 다시 사용되거나 아예 안 쓰이는 것 제거
- `Set<Integer> set = new HashSet`: 현재 멀티탭에 꽂혀 있는 전기용품들
- `cnt`: 플러그를 뽑은 횟수 (정답)
- `int cur = arr[i]`: 지금 사용해야 할 전기용품
// 이미 꽂혀 있는 경우
if (set.contains(cur)) continue;
// 멀티탭에 여유 O
if (set.size() < N) {
set.add(cur);
continue;
}
- `target`: 뽑을 전기용품
- `farthest`: 가장 나중에 다시 쓰이는 시점
- `next`: 전기용품 `s`가 다음에 다시 사용되는 시점
- 다시는 안 쓰임: `Integer.MAX_VALUE`
- 다시 사용됨: 해당 인덱스(`j`)
int target = -1;
int farthest = -1;
for (int s : set) {
int next = Integer.MAX_VALUE;
// 다음 사용 시점
for (int j = i + 1; j < K; j++) {
if (arr[j] == s) {
next = j;
break;
}
}
if (next > farthest) {
farthest = next;
target = s;
}
}
set.remove(target);
set.add(cur);
cnt++;
코드
import java.io.*;
import java.util.*;
// 멀티탭 스케줄링
public class boj_1700 {
static int N, K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int[] arr = new int[K];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < K; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Set<Integer> set = new HashSet<>();
int cnt = 0;
for (int i = 0; i < K; i++) {
int cur = arr[i];
if (set.contains(cur)) continue;
if (set.size() < N) {
set.add(cur);
continue;
}
int target = -1;
int farthest = -1;
for (int s : set) {
int next = Integer.MAX_VALUE;
for (int j = i + 1; j < K; j++) {
if (arr[j] == s) {
next = j;
break;
}
}
if (next > farthest) {
farthest = next;
target = s;
}
}
set.remove(target);
set.add(cur);
cnt++;
}
System.out.println(cnt);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/DP] 백준 11049 - 행렬 곱셈 순서 (Java) (0) | 2025.12.22 |
|---|---|
| [BOJ/Segment Tree] 백준 2042 - 구간 합 구하기 / 10999 - 구간 합 구하기 2 (Java) (0) | 2025.12.20 |
| [BOJ] 백준 1516 - 게임 개발 (Java) (0) | 2025.12.15 |
| [BOJ] 백준 6549 - 히스토그램에서 가장 큰 직사각형 (Java) (0) | 2025.12.14 |
| [BOJ/Simulation] 백준 14499 - 주사위 굴리기 (Java) (0) | 2025.12.05 |