bj1700(멀티탭 스케쥴링)-그리디 *복습*

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

 

이 문제는 그리디 전략은 쉽게 떠올릴 수 있지만, 구현이 까다로웠던 문제다.

그리디 전략은 현재 꼽혀있는 플러그 중 이후로 더이상 안쓰는 플러그나, 다 쓴다면, 제일 먼 미래에 쓸 플러그를 뽑아 교체해주는 것이다.

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

public class Main {
    /**
     * 2 3 2 3 1 2 7 3
     * 2 3 5 7 / / / /
     *
     *
     * 그리디 전략
     * 꽂힌 플러그중 더 안쓰는 플러그나 먼 미래에 쓸 플러그를 뽑는다.
     */
    static int N, K;
    static int[] nums;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(solve());
    }

    private static int solve() {
        Set<Integer> inTap = new HashSet<>();
        int answer = 0;
        for(int i = 0; i < K; i++){
            if(inTap.contains(nums[i]))continue;

            if(inTap.size() < N){
                inTap.add(nums[i]);
                continue;
            }

            pick(i, inTap);
            answer++;
        }
        return answer;
    }

    private static void pick(int tempIndex, Set<Integer> inTap) {
        int maxKey = 0;
        int maxIndex = 0;
        for(int temp : inTap){
            boolean isContain = false;
            for(int i = tempIndex + 1; i < K; i++){
                if(nums[i] == temp){
                    isContain = true;
                    if(i > maxIndex){
                        maxKey = temp;
                        maxIndex = i;
                    }
                    break;
                }
            }
            if(!isContain){
                inTap.remove(temp);
                inTap.add(nums[tempIndex]);
                return;
            }
        }
        inTap.remove(maxKey);
        inTap.add(nums[tempIndex]);
    }

    private static void initialize() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        K = Integer.parseInt(stringTokenizer.nextToken());
        nums = new int[K];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < K; i++){
            nums[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
    }
}