[백준 Baekjoon] 1700번 멀티탭 스케줄링 - JAVA

[백준 Baekjoon] 1700번 멀티탭 스케줄링 - JAVA

---

문제 풀이

그리디 알고리즘을 활용하여 해결할 수 있는 문제였습니다. 멀티탭이 모두 사용중인 경우에 가장 마지막으로 사용되는 콘센트를 찾아 제거하는데 그리디 알고리즘이 사용됩니다.

멀티탭에 꽃혀있는 전기용품을 HashSet을 사용하여 저장하도록 하였습니다.

1. 멀티탭에 콘센트가 전부 사용중이기 전까지(HashSet size < N) HashSet에 추가해줍니다.
2. 멀티탭의 콘센트가 전부 사용중인 경우 남은 전기용품을 순회하여 사용중인 전기용품 중 앞으로의 순서(list)와, 사용하지 않는 전기용품(remain)을 찾습니다. 이 경우 플러그를 빼는 것이므로 answer를 1증가 시킵니다.
3. 전부 사용중인 경우 순서에서 가장 마지막으로 사용될 전기용품을 제거합니다.
4. 전부 사용중이 아닌 경우 사용되지 않는 전기용품을 제거합니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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[] arr = new int[K];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < K; i++) {
            if (!set.contains(arr[i])) {
                if (N <= set.size()) {
                    List<Integer> list = new ArrayList<>();
                    Set<Integer> remain = new HashSet<>(set);

                    for (int j = i; j < K; j++) {
                        if (set.contains(arr[j]) && !list.contains(arr[j])) {
                            list.add(arr[j]);
                            remain.remove(arr[j]);
                        }
                    }

                    if (list.size() == N) {
                        set.remove(list.get(list.size() - 1));
                    } else {
                        List<Integer> temp = new ArrayList<>(remain);
                        set.remove(temp.get(0));
                    }

                    answer++;
                }

                set.add(arr[i]);
            }
        }

        System.out.println(answer);
    }
}