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

🔺 문제

1700번: 멀티탭 스케줄링

 

 

🔺 코드

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[] order = new int[K];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < K ; i++) {
            order[i] = Integer.parseInt(st.nextToken());
        }
        
        boolean[] use = new boolean[101];
        int put = 0;
        int ans = 0;
        
        for(int i = 0 ; i < K ; i++) {
            int tmp = order[i];
            
            // 콘센트가 안 꽂혀있는 경우
            if(!use[tmp]) {
                if(put < N) {   // 콘센트 꽂을 공간이 있는 경우
                    use[tmp] = true;
                    put++;
                }
                else {          // 콘센트 꽂을 공간이 없는 경우
                    ArrayList<Integer> list = new ArrayList<>();    // 현재 꽂힌 콘센트 中 나중에도 사용될 것으로 예측되는 콘센트 정보 담는 리스트
 
                    for(int j = i ; j < K ; j++) {  // 현재 꽂힌 콘센트가 나중에도 사용되는지 확인
                        if(use[order[j]] && !list.contains(order[j])) {
                            list.add(order[j]);     // 추후 사용 여부 확인
                        }
                    }
                    
                    if(list.size() != N) {  // 나중에도 사용되는 콘센트가 구멍 개수보다 작을 경우,
                        for(int j = 0 ; j < use.length ; j++) {
                            if(use[j] && !list.contains(j)) {   // 그 콘센트 제거
                                use[j] = false;
                                break;
                            }
                        }
                    }
                    else {  // 현재 꽂힌 모든 콘센트가 나중에도 사용될 경우,
                        int remove = list.get(list.size() - 1); // 가장 마지막에 사용될 콘센트 제거
                        use[remove] = false;
                    }
                    
                    use[tmp] = true;
                    ans++;
                }
            }
        }
        
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}
 

✅ 해결 아이디어
✔ 그리디
- 페이지 교체 알고리즘

 

 

---

🔺 다른 풀이들

- 상세 설명 굿..

백준 1700번: 멀티탭 스케줄링 (JAVA)

 

 

---

💬 느낀 점

페이지 교체 알고리즘을 이렇게 써먹는구나...

정처기 암기할 때 보기만 했었는데....

익숙해져보자...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ] 백준 1700번 : 멀티탭 스케줄링 (JAVA)