[알고리즘] 백준 > #1700. 멀티탭 스케줄링

문제링크

백준 #1700. 멀티탭 스케줄링

풀이방법

곰곰~히 생각해보면 그리디 알고리즘으로 해결할 수 있는 문제입니다. 당장 눈 앞의 이익만 좇는 방법이 그리디 알고리즘이죠? 이 문제도 새로운 콘센트를 꽂아야 할 때 앞으로 가장 오랫동안 사용되지 않을 콘센트를 골라 뽑으면 되는 눈 앞의 이익만 좇는 방법입니다 ㅎㅎ(페이지 교체 알고리즘 중 최적 페이지 교체 알고리즘 같네욥)

위에서 말한 알고리즘을 다른 케이스와 같이 설명해보면 다음과 같습니다.
case1. 이미 해당 콘센트가 꽂혀 있는 경우 -> continum
case2. 멀티탭에 자리가 남은 경우 -> 꽂기
case3. 멀티탭에 자리가 없고 새로운 콘센트인 경우 -> 앞으로 가장 오랫동안 사용되지 않을 콘센트자리에 꽂기

간단하네용..ㅎㅎ..

코드

import java.util.*;

public class MultitapScheduling {
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        Integer[] devices = new Integer[k];
        for (int i = 0; i < k; i++) {
            devices[i] = sc.nextInt();
        }

        int countPop = 0;

        List<Integer> multitap = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            Integer device = devices[i];
            int index = multitap.indexOf(device);
            if (index != -1) continue;
            else {
                if (multitap.size() < n) multitap.add(device);
                else {
                    LinkedList<Integer> list = new LinkedList<>();
                    list.addAll(multitap);

                    int nextDeviceIndex = i + 1;
                    while ((list.size() > 1) && (nextDeviceIndex < k)) {
                        list.remove(devices[nextDeviceIndex++]);
                    }

                    index = multitap.indexOf(list.getFirst());
                    multitap.set(index, device);

                    countPop++;
                }
            }
        }

        System.out.print(countPop);
    }
}