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

문제의 링크 : https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 

• 키보드
• 헤어드라이기
• 핸드폰 충전기
• 디지털 카메라 충전기
• 키보드
• 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다. 

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오. 

 

풀이

그리디 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 멀티탭 구멍의 개수가 넉넉할 경우에는 그냥 콘센트를 꽂으면 되지만, 자리가 없는 경우에 어떻게 꽂혀있는 콘센트를 빼야하는지가 관건이었습니다. 그리고 이렇게 빼는 과정에서 그리디 알고리즘을 적용하면 됩니다. 먼저, 전반적인 로직을 봅시다.

1. 사용하려는 전기 용품의 콘센트가 꽂혀있는 경우, 아무런 행동도 취할 필요 없다.

2. 사용하려는 전기 용품의 콘센트가 꽂혀있지 않은 경우.

2-1. 멀티탭의 구멍이 넉넉하다면, 비어있는 아무 공간에 콘센트를 꽂는다.

2-2. 멀티탭의 구멍이 넉넉하지 않은 경우, 현재 꽂혀있는 콘센트들이 나중에도 사용되는지 확인한다.

2-2-1. 현재 꽂혀있는 콘센트들 중 일부만 나중에 사용된다면, 나중에도 사용되지 않는 콘센트를 제거하고, 현재 사용하려는 콘센트를 꽂는다.

2-2-2. 현재 꽂혀있는 콘센트 모두 나중에 사용된다면, 그 중 그나마 가장 늦게 사용되는 콘센트를 제거하고, 현재 사용하려는 콘센트를 꽂는다.

 

2-2번 과정에서 그리디 알고리즘이 사용된다는 점을 주의깊게 보시길 바랍니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        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 temp = order[i];
 
            if (!use[temp]) { // 콘센트가 꽂혀있지 않은 경우
                if (put < N) { // 콘센트를 꽂을 공간이 있는 경우
                    use[temp] = true;
                    put++;
                } else { // 콘센트를 꽂을 공간이 없는 경우
                    ArrayList<Integer> arrList = new ArrayList<>();
                    for (int j = i; j < K; j++) { // 현재 꽂혀 있는 콘센트가 나중에도 사용되는지 확인.
                        if (use[order[j]] && !arrList.contains(order[j])) {
                            arrList.add(order[j]);
                        }
                    }
 
                    if (arrList.size() != N) { // 나중에도 사용되는 콘센트가 구멍의 개수보다 작을 경우.
                        for (int j = 0; j < use.length; j++) {
                            if (use[j] && !arrList.contains(j)) { // 그 콘센트를 제거.
                                use[j] = false;
                                break;
                            }
                        }
                    } else { // 현재 꽂혀 있는 모든 콘센트가 나중에도 사용될 경우
                        int remove = arrList.get(arrList.size() - 1); // 가장 마지막에 사용될 콘센트를 제거.
                        use[remove] = false;
                    }
 
                    use[temp] = true;
                    ans++;
                }
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.