[BOJ] 1700: 멀티탭 스케줄링 (JAVA)

문제

https://www.acmicpc.net/problem/1700

 

여담

풀이 방법은 떠올렸지만 구현하는 데에서 많은 시간을 썼다.. 처음에는 substring()을 사용해서 위치를 찾으려고 했는데 생각보다 고려해야 할 것이 많았고, 반례를 잡지 못했다.

 

다른 분이 ArrayList를 사용한 것을 보고 "이걸 왜 못 떠올렸지..?"라는 생각이 들었고, 결국 문자열에서 ArrayList를 사용하는 것으로 방법을 틀었다.

 

생각보다 시간이 많이 소요됐고 구현하는 것에서 문제가 있었기 때문에 빠른 시일 내에 다시 또 풀어봐야 되겠다..!

 

풀이

이 문제는 그리디 알고리즘을 사용하는 문제로, 가장 중요한 것은 플러그를 빼는 횟수의 최솟값을 얻기 위해 어떤 행동을 해야 하는 가를 떠올리는 것이다.

 

빼는 횟수의 최솟값을 얻으려면 꽂혀있는 플러그들 중에서, 앞으로 사용되지 않는 플러그나 가장 늦게 사용하는 플러그를 뽑아야 한다.

 

따라서 풀이 로직은 다음과 같다.

1. 멀티탭에 플러그를 꽂을 자리가 남아있는 경우
   • 플러그를 꽂으면 됨
   • multiTab.add(plug)
2. 사용하려는 플러그가 이미 멀티탭에 꽂혀 있는 경우
   • 그냥 넘어가면 됨
3. 사용하려는 플러그가 멀티탭에 꽂혀 있지 않는 경우
   • 해당 플러그가 더 이상 사용되지 않거나 가장 늦게 사용되는 플러그 찾기
   • ArrayList를 사용하면 contains() 메소드와 indexOf() 메소드를 이용해서 쉽게 확인하고 찾을 수 있음
     • 더 이상 사용되지 않는 경우: !plugList.contains(tab)
     • 플러그가 사용되는 위치: plugList.indexOf(tab)

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 제일 늦게 사용하는거 or 이제 사용안하는거 뽑는것이 최소 뽑는 횟수
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        ArrayList<Integer> plugList = new ArrayList<>();
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < k; i++) {
            plugList.add(Integer.parseInt(st.nextToken()));
        }

        int offNum = 0;
        HashSet<Integer> multiTab = new HashSet<>();
        for (int i = 0; i < k; i++) {
            int plug = plugList.remove(0);
            if (multiTab.size() < n) { // 멀티탭에 플러그를 꽂을 자리가 남아있는 경우
                multiTab.add(plug);
            } else if (!multiTab.contains(plug)) { // 멀티탭에 해당 플러그가 꽂혀있지 않은 경우
                int removePlug = -1, removeIdx = -1;
                for (int tab : multiTab) {
                    // 해당 플러그가 더 이상 사용되지 않는 경우
                    if (!plugList.contains(tab)) {
                        removePlug = tab;
                        break;
                    }
                    // 모든 플러그가 사용된다면 가장 늦게 사용되는 플러그 찾기
                    int idx = plugList.indexOf(tab);
                    if (removeIdx < idx) {
                        removePlug = tab;
                        removeIdx = idx;
                    }
                }
                offNum++;
                multiTab.remove(removePlug);
                multiTab.add(plug);
            }
        }
        System.out.println(offNum);
    }
}

---

참고

https://kkmdailylog.tistory.com/entry/AlgorithmJava%EB%B0%B1%EC%A4%80-1700%EB%B2%88-%EB%A9%80%ED%8B%B0%ED%83%AD-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81