[백준][boj] 멀티탭 스케줄링(1700) - JAVA

✔ 문제 파악

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

 

 

---

 

 

✔ 문제 풀이

그리디 알고리즘 문제이다.

그리디 알고리즘이란?
매 선택에서 당장 눈 앞에 보이는 최적의 상황만 쫓아 최종적인 해답에 도달하는 방법이다.

 

그리디 유형에서 가장 중요한 것은, 그리디 유형인지 알아보는 것이다 ! (당연한 말씀을.. )  

최소한으로 제품을 뽑아내면서 모든 제품을 사용할 수 있도록 멀티탭을 관리하기 위해서 생각난 알고리즘은

OPT 알고리즘이다. 

 

OPT알고리즘은 페이지 교체 알고리즘 중 하나로, 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.

그렇게 때문에 우리는 현재 상황에서 앞으로 가장 오랫동안 사용하지 않을 플러그를 빼버리고 지금의 플러그를 꽂아줄 것이다.

 

크게 2가지 상황으로 나눌 수 있다.

 

1. 멀티탭 구멍이 꽉 차지 않았을 경우

-> 그냥 꽂아준다.

 

2. 멀티탭 구멍에 사용하려는 기기가 이미 꽂혀있을 경우

-> pass ~ 

 

3. 멀티탭이 꽉 찼을 경우

-> 앞으로 가장 늦게 사용되거나, 더 이상 사용되지 않은 제품을 뽑아준다.

 

 

핵심 코드는 다음과 같다.

Set<Integer> tabs = new HashSet<>();

for (int i = 0; i < m; i++) {
    int obj = arr[i];

    // 1. 멀티탭 구멍이 꽉 차지 않았을 경우
    if (tabs.size() < n) {
        tabs.add(obj);
    // 2. 멀티탭 구멍에 사용하려는 기기가 이미 꽂혀있을 경우
    } else if (tabs.contains(obj)) {
        continue;
    // 3. 멀티탭이 꽉 찼을 경우
    } else {

        // 이후 사용될 기기들의 인덱스를 저장해준다.
        Map<Integer, Integer> map = new HashMap<>();
        for (int k = i + 1; k < m; k++) {
            map.put(arr[k], k);
        }

        int remove = -1;
        int removeIdx = -1;

        for (int tab : tabs) {
            // 만약에 앞으로 사용되지 않는 플러그가 있다면 빼준다.
            if (!map.containsKey(tab)) {
                remove = tab;
                break;
            } else {
                // 가장 나중에 사용될 플러그가 빼줘야할 플러그 !
                if (removeIdx < map.get(tab)) {
                    removeIdx = map.get(tab);
                    remove = tab;
                }
            }
        }

        // 플러그 빼주고
        tabs.remove(remove);
        answer++;

        // 현재 플러그 꽂아주기
        tabs.add(obj);
    }
}

 

 

---

 

 

✔ 전체 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int answer = 0;

        st = new StringTokenizer(br.readLine());

        int[] arr = new int[m];

        for (int i = 0; i < m; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }


        Set<Integer> tabs = new HashSet<>();

        for (int i = 0; i < m; i++) {
            int obj = arr[i];

            if (tabs.size() < n) {
                tabs.add(obj);
            } else if (tabs.contains(obj)) {
                continue;
            } else {
                Map<Integer, Integer> map = new HashMap<>();
                for (int k = i + 1; k < m; k++) {
                    if (map.containsKey(arr[k])) {
                        map.put(arr[k], k);
                }

                int remove = -1;
                int removeIdx = -1;
                for (int tab : tabs) {
                    if (!map.containsKey(tab)) {
                        remove = tab;
                        break;
                    } else {
                        if (removeIdx < map.get(tab)) {
                            removeIdx = map.get(tab);
                            remove = tab;
                        }
                    }
                }

                tabs.remove(remove);
                answer++;
                tabs.add(obj);
            }
        }
        System.out.println(answer);
    }
}

 

 

---

 

❤ 회고

☆*: .｡. o(≧▽≦)o .｡.:*☆ 알고리즘 고수가 되는 그날까지 ~!