[BOJ/Greedy] 백준 1700 - 멀티탭 스케줄링 (Java)

백준 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);
    }
}