백준 1700번 멀티탭 스케줄링 - 자바(JAVA)

문제 링크

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

 

 

---

1. 문제

2. 문제 관찰 과정 및 풀이

2-1. 문제 관찰 과정

 

cpu 스케줄링이 생각나는 문제 였다.

처음의 풀이는 입력을 받으면서 count배열을 만들어서 각 숫자의 인덱스 값을 증가 시켜 가장 많이 나오는 수를

체크해서 가장 적게 나오는 플러그를 교체하는 방식으로 풀었는데 내가 생각하는 테스트 케이스에서는 답이 잘 나왔었지만 계속 틀림이 떴엇다.

 

그래서 반례에서 계속 통과 못한다는 것을 알고 내가 생각해도 좀 답이 틀릴 경우가 있을 것 같아 다른 알고리즘을 생각하게 되었다.

 

틀린 코드

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

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[] arr = new int[k];
        int[] count = new int[101];
        Set<Integer> set = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            arr[i] = tmp;
            count[tmp]++;
        }

        int answer = 0;
        for (int i = 0; i < k; i++) {
            int tmp = arr[i];
            if (set.contains(tmp)) {
                continue;
            }

            if (set.size() == n) { //콘센트가 꽉참
                int min = 0;
                for (int num : set) { //제일 적은 횟수인 플러그
                    if (min == 0 || count[num] < count[min]) {
                        min = num;
                    }
                }
                set.remove(min);
                set.add(tmp);
                answer++;
            } else { //컨센트 여유
                set.add(tmp);
            }
        }
        bw.write(answer + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

2-2. 문제 풀이

바꾸는 우선 순위는 우선

1. 뒤에 등장하지 않는 플러그는 볼것도 없이 그냥 교체 해준다.
2. 플러그가 나오는 위치를 기록해두고 있다가 콘센트의 리스트중에서 가장 나중에 바뀌는 플러그를 교체
3. 콘센트가 비어있다면 추가

라는 계획을 세웠고 플러그가 바뀔 위치를 기록하기 위해 맵을 이용해서 각 플러그마다 등장하는 인덱스를 기록해 두었다.

그리고 플러그에 끼울때 해당 인덱스를 삭제 한다.

플러그를 교체해야 할때에는 가장 최신의 인덱스를 확인하고 가장 큰 인덱스를 가진 플러그를 삭제하고 교체해준다.

3. 코드

//백준
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));
        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[] arr = new int[k];
        Map<Integer, List<Integer>> map = new HashMap<>();
        Set<Integer> set = new HashSet<>(); //콘센트

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            arr[i] = tmp;
            map.putIfAbsent(tmp, new LinkedList<>());
            map.get(tmp).add(i);
        }

//        System.out.println(map.toString());
        int answer = 0;

        //2 3 2 3 1 2 7
        for (int i = 0; i < k; i++) {
            int tmp = arr[i];
            if (set.contains(tmp)) {
                map.get(tmp).remove(0); //앞에 있는거 지움
                continue;
            }
            if (set.size() == n) { //콘센트 꽉참
                int next = 0; //조건 1부터라서
                for (int flug : set) {
                    //콘센트의 플러그중에 가장 나중에 쓰거나 안쓰는거
                    //체크
                    if (map.get(flug).isEmpty()) {
                        next = flug;
                        break;
                    }
                    if (next == 0 || map.get(flug).get(0) > map.get(next).get(0)) {//다음거중에 제일 큰거
                        next = flug;
                    }
                }
                set.remove(next);
                set.add(tmp);
                map.get(tmp).remove(0);
                answer++;
            } else { //자리 비어 있다면
                set.add(tmp);
                map.get(tmp).remove(0);
            }
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

3-1. 실행 결과

4. 여담

100ms미만으로 나오는 코드들도 있던데 참고를 해봐야할 것 같다.

아마 LinkedList를 사용하면서 구현되는 과정에서 시간차이가 나는것 같다.