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

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

문제분석

그리디 알고리즘 연습을 위한 문제이다 보니, '부분 최적해' 를 구하기 위해 노력하였다.

플러그 구멍이 남는 경우, 제품이 이미 꽃혀있는 경우들은 문제가 아니므로 제외한다. 따라서 생각해야 하는 문제는 아래와 같다.

플러그가 가득 찼을 때, 새 플러그를 꽃기 위해 뽑아야 하는 플러그는 무엇인가?

가장 처음 생각한 부분 최적해는 '남은 횟수가 적은 제품 먼저 플러그를 뽑을 것' 이다. 이 방식으로 문제를 풀어보니, 다음 반례에 막히게 된다.

2 9

1 2 3 1 2 3 1 2 3

4가 나오지 않는 문제에 직면했다. 따라서 부분 최적해를 잘못 설정했다는 것을 알 수 있었다.

이후, 두번째로 생각한 것은 '사용할 제품부터 N개를 확인한 후, 가장 뒤에 있는 제품부터 플러그를 뽑을 것' 였다. 하지만 말도 안되게 많은 예외처리를 보고, 잘못 방향을 잡았다는 생각이 들었다.

마지막으로 생각한 것은, '꽃혀있는 제품 중 가장 늦게 다시 쓸 제품부터 뽑을 것' 였다. 다행이 이 방법이 맞았고, 예외처리를 하다보니 정답을 맞을 수 있었다.

정답 코드

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 멀티탭 구멍의 개수
        int K = Integer.parseInt(st.nextToken()); // 전기 용품의 총 사용횟수

        // int[] arr = new int[K]; // 해당 제품 몇번 남았는지 확인하기 위함
        // Arrays.fill(arr,0);
        Map<Integer, Integer> map = new HashMap<>(); // 해당 제품 몇번 남았는지 확인하기 위함

        ArrayList<Integer> list = new ArrayList<Integer>(); // 순서대로 저장용

        st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            int product = Integer.parseInt(st.nextToken());
            // arr[product-1] = arr[product-1]+1;

            if(map.containsKey(product)){
                map.put(product,map.get(product)+1);
            }else{
                map.put(product,1);
            }

            list.add(product);
        }
        int result = 0;
        ArrayList<Integer> plugList = new ArrayList<Integer>(); // 플러그에 들어가는 제품 리스트
        for (int i = 0 ; i < K ; i++){
            int product = list.remove(0);
            if(plugList.contains(product)){ // 플러그에 이미 꽃혀있는 경우
                map.put(product,map.get(product)-1);
            }else if(plugList.size()<N){ // 플러그가 여유있는 경우
                plugList.add(product);
                map.put(product,map.get(product)-1);
            }
            else{ // 플러그에 여유 없는 경우
                boolean flag = false;
                int useless = 0 ;
                int oldestProduct = 0;
                int old = 0;
                for(int p : plugList){
                    int nextIdx = list.indexOf(p);  // 각 제품들의 '다음 첫 번째 사용 index', 가장 큰 값 제거
                    if(nextIdx>=old){
                        oldestProduct = p;
                        old = nextIdx;
                    }

                    if(map.get(p)==0){ // plugList 중 남은 사용횟수 0 있는지 여부
                        flag = true;
                        useless = p;
                    }
                }

                result++;
                if (flag){ // 남은 사용횟수 0 존재(map.get(useless)==0, 건들 필요 x)

                    plugList.remove(Integer.valueOf(useless));
                    plugList.add(product);
                    map.put(product,map.get(product)-1);

                }else{// 남은 사용횟수 0 존재하지 않음, 가장 늦게 사용하는 제품부터 제외 시도

                    plugList.remove(Integer.valueOf(oldestProduct));
                    plugList.add(product);
                    map.put(product,map.get(product)-1);
                }

            }
        }
        bw.write(String.valueOf(result));
        bw.newLine();
        bw.flush();
        bw.close();

    }
}