[백준 1700 / JAVA] 머리탭 스케줄링

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

1700번: 멀티탭 스케줄링

 

간단히 말해 멀티탭에 연결한 플러그를 빼는 횟수를 최소화시키는 문제이다.

 

처음에는 남은 용품의 각각의 수를 계산하고 가장 적게 남은 상품을 교체하는 방식으로 잘못 풀었다.

 

올바른 방식은 다음 용품을 꽂아야 할 때 빼야 하는 플러그를 구하는 기준은 이후에 꽂는 순서가 가장 뒤인 용품이다.

예를 들어)2 7 / 2 3 2 3 1 2 7 에서 네번째 용품까지는 플러그를 뺄 일이 없다.

1을 연결해야 할 때 남은 용품인 2 7 에서 2가 먼저 오므로 3을 뺀다.

이런식으로 가장 나중에 사용되는 용품을 먼저 빼도록한다.

 

int i = 0;
        while (i < K) {
            if (!checkPlug(a[i])) { // 같은 번호가 플러그에 없을 때
                int change = choosePlug(i + 1);
                if (plug[change] != 0) { // 플러그를 바꿔야 할 때
                    result++;
                }
                plug[change] = a[i]; // 플러그 변경
            }

            i++;
        }

checkPlug 메서드는 같은 용품이 이미 플러그에 꽂혀있는지 확인하는 메서드이다.

choosePlug 메서드는 다음으로 빼야하는 플러그의 인덱스를 구하는 메서드이다.

 

    // 이미 같은 제품이 플러그에 있는지 확인
    public static boolean checkPlug(int a) {
        for (int i = 0; i < N; i++) {
            if (plug[i] == a)
                return true;
        }
        return false;
    }

같은 제품이 플러그에 있는지 확인한다.

 

    // 바꿀 플러그 확인
    public static int choosePlug(int next) {
        int result = 0, temp = 0, j;
        for (int i = 0; i < N; i++) {
            if (plug[i] == 0) // 빈 플러그가 있다면 선택
                return i;

            // 가장 먼저 사용되는 인덱스
            for (j = next; j < K; j++) {
                if (plug[i] == a[j])
                    break;
            }

            //더 늦게 사용되는 상품 저장
            if (j > temp) {
                temp = j;
                result = i;
            }
        }

        return result;
    }

만약 빈 플러그가 있다면 바로 그 인덱스를 반환한다.

아니라면 현재 인덱스의 플러그의 용품이 다음으로 언제 다시 사용되는지 확인하고

다시 사용되는 순서가 가장 늦는 제품을 꽂은 플러그의 인덱스를 찾는다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, K;
    static int[] a, plug;

    public static void main(String[] args) throws IOException {
        String input;
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int result = 0;
        input = br.readLine();
        st = new StringTokenizer(input);

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        plug = new int[N]; // 플러그 상태
        a = new int[K]; // 입력

        int t;
        input = br.readLine();
        st = new StringTokenizer(input);
        for (int i = 0; i < K; i++) {
            t = Integer.parseInt(st.nextToken());
            a[i] = t;
        }

        int i = 0;
        while (i < K) {
            if (!checkPlug(a[i])) { // 같은 번호가 플러그에 없을 때
                int change = choosePlug(i + 1);
                if (plug[change] != 0) { // 플러그를 바꿔야 할 때
                    result++;
                }
                plug[change] = a[i]; // 플러그 변경
            }

            i++;
        }

        System.out.println(result);
    }

    // 이미 같은 제품이 플러그에 있는지 확인
    public static boolean checkPlug(int a) {
        for (int i = 0; i < N; i++) {
            if (plug[i] == a)
                return true;
        }
        return false;
    }

    // 바꿀 플러그 확인
    public static int choosePlug(int next) {
        int result = 0, temp = 0, j;
        for (int i = 0; i < N; i++) {
            if (plug[i] == 0) // 빈 플러그가 있다면 선택
                return i;

            // 가장 먼저 사용되는 인덱스
            for (j = next; j < K; j++) {
                if (plug[i] == a[j])
                    break;
            }

            //더 늦게 사용되는 상품 저장
            if (j > temp) {
                temp = j;
                result = i;
            }
        }

        return result;
    }
}