[백준 1700] 멀티탭 스케줄링 / 자바 / 그리드

#문제         

레벨: G1
알고리즘: 그리드 
풀이시간: 30분
힌트 참조 유무:

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

---

#문제 풀이       

이 문제는 순서대로 조건에 맞게 하나 씩 콘센트를 빼고 꽂는다 하여 그리드 문제이다. 그리드는 지금까지 탐색한 것들을 토대로 풀어나간다 라는 생각이 있어서 이 방식도 그리드인줄 몰랐다. 그래서 이 방식이 뭐냐? 꽂을려는 콘센트가 이미 꽂혀있는 경우는 skip하고 구멍이 넉넉한 경우에도 꽂아주고 skip한다. 신경써줘야 할 부분은 구멍이 다 꽂혀있을 경우인데 콘센트를 뽑을지는 가장 뒤늦게 다시 나오는 콘센트를 뽑는 거다. 그러기 위해서는 앞이 아닌 뒤를 탐색해야 한다. 

이번 문제를 통해서 그리드 개념을 다시 세웠다. 현재까지 탐색한 것을 토대로 답을 도출해내는 것이 아니라, 현재에서 번복하지 않을 최적의 답을 구하는 것이 그리드이다.

---

#풀이 코드      

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        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()); // 전기용품의 총 사용횟수
        
        int[] order = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            order[i] = Integer.parseInt(st.nextToken());
        }
        
        Set<Integer> plugged = new HashSet<>();
        int result = 0;
        
        for (int i = 0; i < K; i++) {
            int current = order[i];
            
            if (plugged.contains(current)) {  //이미 꽂혀있을 때 skip
                continue;
            }
            
            if (plugged.size() < N) {  //구멍이 넉넉할 때  꽂아주고 skip
                plugged.add(current);
            } else {
                int toRemove = -1;
                int farthest = -1;
                
                for (int plug : plugged) {  //꽂혀있는 것중에 가장 뒤늦게 나오는 걸 뽑음
                    int next = K;  // 기본값을 K로 설정 (더 이상 사용되지 않음을 의미)
                    for (int j = i + 1; j < K; j++) {
                        if (order[j] == plug) {
                            next = j;
                            break;
                        }
                    }
                    
                    if (next > farthest) {
                        farthest = next;
                        toRemove = plug;
                    }
                }
                
                plugged.remove(toRemove);
                plugged.add(current);
                result++;
            }
        }
        
        System.out.println(result);
        br.close();
    }
}