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

문제

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

1700번: 멀티탭 스케줄링

풀이

최대한 적게 멀티플러그를 빼는 문제. 

게시판 반례 참고해서 코드 수정 하였다.  풀이는 다음과 같다. 

1. 현재 멀티탭이 구멍보다 작을 때  플러그를 꽃는다.
2. 멀티탭 남는 구멍이 없어 플러그를 빼야 하면, 다음 등장하는 인덱스가 가장 큰 것을 플러그에서 제거한다. 
3. 이미 멀티탭에 있는 번호가 나왔으면, 다음 등장 인덱스를 업데이트 해준다. 

먼저 해시맵을 사용해서 현재 기준 cur 에서 다음 번째 등장 인덱스를 메모해주었다. 

		for(int i =0  ;i <k ;i++){
            int a = nums[i];
            if(map.containsKey(a)) {//다음 등장 번호 메모한다.
                dist[map.get(a)] = i;
            }
                map.put(a,i);
        }

그다음 내림차순 정렬 트리셋을 이용하여 수도 코드 2번 3번을 풀이하였다. 

 

TreeSet<Integer> ts = new TreeSet<>((a,b)->b-a); //내림차순 정렬

그다음 배열 끝까지 순회하면서 트리셋에 있으면 업데이트, 멀티탭 구멍 남으면 추가, 트리셋에 없는데 빼야 하면 pollFirst()를 하였다. 

		for(; left < k ;left++){
            if(ts.contains(left)){
                ts.remove(left);
                ts.add(dist[left]);
            }else if(ts.size() < n){
                ts.add(dist[left]);
            }else{
                ts.pollFirst();
                ts.add(dist[left]);
                ans++;
            }
        }

참고

처음에 멀티탭을 n 만큼 꽂을때 중복 처리를 안해주어서 8퍼센트에서 에러가 떴다... 주의하길 바란다. 

 

코드

자바

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

public class Main {
    int n, k;
    int nums[];
    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.sol();
    }
    public int getN(){
        HashMap<Integer, Integer>map = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();
        int dist[] = new int[k];
        dist[0] = 1001;
        for(int i = 1 ;i < k;i++)
            dist[i] = dist[i-1]+1;

        for(int i =0  ;i <k ;i++){
            int a = nums[i];
            if(map.containsKey(a)) {
                dist[map.get(a)] = i;
            }
                map.put(a,i);
        }
        //System.out.println(Arrays.toString(dist));
        //int[]{num, nextAppearance} ;
        TreeSet<Integer> ts = new TreeSet<>((a,b)->b-a);

        int left =0;
        while(left < k && ts.size() < n){
            if(ts.contains(left)){
                ts.remove(left);
            }
            ts.add(dist[left++]);
        }

        int ans =0;

        for(; left < k ;left++){
            if(ts.contains(left)){
                ts.remove(left);
                ts.add(dist[left]);
            }else if(ts.size() < n){
                ts.add(dist[left]);
            }else{
                ts.pollFirst();
                ts.add(dist[left]);
                ans++;
            }
        }
        return ans;
    }
    public void sol() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String q = br.readLine();
        n= Integer.parseInt(q.split(" ")[0]);
        k= Integer.parseInt(q.split(" ")[1]);
        nums = new int[k];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0; i< k;i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(getN());
    }


}