[BOJ] 1700 멀티탭 스케줄링

멀티탭 스케줄링

풀이

• 멀티탭 구멍의 개수 N, 전기 용품의 총 사용횟수 K.
• 전기 용품 이름이 K 이하의 자연수로 사용순서대로 주어진다.
• 하나씩 플러그를 빼는 최소의 횟수를 구해라.
• 예를 들어, 2 3 2 3 1 2 7 이 사용순서라면, 제일 나중에 쓰거나 아예 안쓴 애를 멀티탭에서 제거해야겠다! 라고 생각 했음.
• 그럼 얘를 나중에 쓴다는걸 어떻게 알지...? 라는 생각에 HashMap에 저장해야겠다고 생각.
  • HashMap<Integer, LinkedList<Integer>> 를 만들어서, key는 입력받는 전기용품의 이름(2,3...) , value는 그 전기용품이 등장하는 idx를 List로 저장하고, 오름차순 정렬했다. 위 예시에서는, key=2, List={0,2,6} 이런식으로 저장한 꼴.
• 그다음, 전기용품 입력받은 배열을 순회하는데, 현재 멀티탭 구멍의 개수보다 꽂힌 전기용품 개수가 적고, 아직 꽂힌적 없는 전기용품인 경우 multitab 리스트에 offer했다.
• 만약 이미 전기용품 꽂혀져 있으면,(멀티탭 리스트에 존재하면) continue,
• 전기용품이 N개 다 꽂혀있으면, 이제 제일 나중에 나올 전기용품 아니면 안나올 전기용품을 multitab 리스트에서 제거해야 한다.
  • 현재 보고 있는 전기용품 배열의 인덱스 이후로 꽂아야 하는 전기용품들을 hashmap에서 탐색하여 후보로 저장.
  • 후보들 순회하면서, 가장 나중에 나오는 전기용품 후보를 찾아서 multitab 리스트에서 제거한다. 그리고 multab에 이제 꽂아야 하는 전기용품을 추가.
  • 제거하는 횟수를 세야하니까, 이 때 answer++

🙆‍♀️ 정답 풀이

import java.util.*;
import java.io.*;
public class BOJ1700 {
    public static void main(String[] args) throws Exception{
        HashMap<Integer,LinkedList<Integer>> map = new HashMap<>();
        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());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[K];
        for(int i=0;i<K;i++){
            int key =Integer.parseInt(st.nextToken());
            arr[i] = key;
            LinkedList<Integer> idxQueue;
            if(map.containsKey(key)){
                idxQueue = map.get(key);
                idxQueue.offer(i);
                Collections.sort(idxQueue); //오름차순 정렬
                map.put(key,idxQueue);
            }
            else{
                idxQueue= new LinkedList<>();
                idxQueue.offer(i);
                map.put(key,idxQueue);
            }
        }
        //멀티탭 꽂을거
        LinkedList<Integer> multitab = new LinkedList<>();
        int ans = 0;
        for(int i=0;i<K;i++){
            if(multitab.contains(arr[i])) continue;
            if(multitab.size()==N){
                int[] delArr = new int[multitab.size()];       //i 인덱스 이후에 나오는 idx 넣기
                Arrays.fill(delArr,-1);
                boolean isFind= false;                          //i 인덱스 이후가 아예 없다면, 얘가 빠지면 됨 그래서 break
                int delIdx = -1;                                //얘가 빠져야 할 경우, idx 저장하려고 만든 변수
                for(int s=0;s<multitab.size();s++){
                    int idx = multitab.get(s);
                    LinkedList<Integer> idxList = map.get(idx);     //해당 제품이 등장하는 인덱스 리스트
                    int temp = -1;
                    for(int m=0;m<idxList.size();m++){
                        if(idxList.get(m)>i){
                            temp = idxList.get(m);                  // i 보다 큰 idx에서 해당 제품이 나오는 경우, 삭제 후보이므로 temp에 저장
                            break;
                        }
                    }
                    if(temp==-1){
                        delIdx = s;
                        isFind = true;
                        break;
                    }
                    else{
                        delArr[s] = temp;                      //삭제 후보 tempArr에 저장
                    }
                }
                if(isFind) {
                    // i 이후로 등장하지 않아서 바로 삭제하면 되는 경우
                    multitab.remove(delIdx);
                    multitab.offer(arr[i]);
                }
                else{
                    // 삭제 후보들 돌면서, 가장 큰 애를 찾으면 됨.(가장 나중에 나온다는 거기 때문에)
                    int maxVal = -1;
                    int maxIdx = -1;
                    for(int a=0;a<delArr.length;a++){
                        if(delArr[a]>maxVal) {
                            maxVal = delArr[a];
                            maxIdx = a;
                        }
                    }
                    //가장 나중에 나오는 애를 찾아서 지우고 해당 arr[i] 를 넣어주기
                    multitab.remove(maxIdx);
                    multitab.offer(arr[i]);
                }
                ans++;
            }
            else if(multitab.size()<N){
                multitab.offer(arr[i]);
            }
        }
        System.out.println(ans);
    }
}

• 코드가 꽤 긴데,,, 그래두 내 힘으로 풀었다. !! 작년 알고리즘 스터디 때 못풀어서 포기했던 문젠데...😁

• 다른 사람 코드를 보니까, hashmap 쓸 필요 없이 그냥 List만 이용해서 멀티탭에서 제거할 우선순위를 구할 수 있다. 나랑 로직은 같은데 난 좀 복잡하게 푼거 같은....