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

#1700 멀티탭 스케줄링

난이도 : 골드 1

유형 : 그리디 

1700번: 멀티탭 스케줄링

▸ 문제

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

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

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

처음에 설계했던 그리디 최적 선택 방식은 전체 사용 순서에서 가장 적게 사용되는 순서부터 교체 시켜주도록 설계를 하였다. 그래서 우선순위 큐로 사용량에 따라 오름차순으로 정렬을 하여 풀이를 하였지만 28%에서 실패가 떴다. 다시 생각해보면 가장 많이 사용되었더라도 순서 배치가 맨 처음과 맨 끝 부분에 위치해있다면 중간에 다른 기기들의 사용 빈도가 더 많은 경우 최적해를 포함할 수 없음을 알 수 있었다.

 

그래서 다음으로 생각해낸 탐욕스런 선택 방식으로 '현재 꽂아져 있는 기기들 중 가장 나중에 사용되는 기기 플러그를 뺀 다음 새로운 기기를 꽂아 넣는다.'를 생각해봤다.  

 

탐욕스런 선택 조건 증명

현재 꽂아져 있는 플러그가 (2,3)이고 현재 1번 기기를 사용하기 위해 플러그를 하나 빼야한다고 하자. 2번 기기는 5차례 이후에 다시 사용하고 3번 기기는 10차례 이후 다시 사용한다고 하면, 2번 기기를 선택할 경우 5차례 이후에 다시 플러그를 빼야 하는 경우가 발생하고 3번 기기를 선택할 경우 10차례 이후에 다시 플러그를 빼야하는 경우가 발생하게 된다.

 

따라서, 3번기기를 뽑는 것이 2번기기를 뽑는 것 보다 더 긴 시간동안 플러그를 바꿀 확률이 더 같거나 낮아지게 되므로 해당 방식이 그리디한 선택임을 알 수 있으므로  '현재 꽂아져 있는 기기들 중 가장 나중에 사용되는 기기 플러그를 빼는 최적해가 존재한다'는 참임을 알 수 있다.

 

가장 나중에 사용되는 기기를 뽑을 경우 해당 플러그 사용 자유기간이 더 높은 확률로 보존된다.

 

설계

1. 전기용품 사용 순서에 따라 탐색을 시작한다. list 0 ~ k
2. set 자료구조를 이용하여 멀티탭에 꽂은 전기용품을 저장한다.
   1. 현재 꽂아져 있는 전기용품이면 해당 탐색은 패스한다. if(set.contains(num)) continue;
   2. 멀티탭 구멍 갯수(n)보다 꽂아져있는 전기용품 갯수가 작고 중복이 되지 않는다면 새롭게 추가하고 나머지 탐색을 패스한다. if(set.size()<n && set.add(num)) continue;
3. 새로운 전기용품을 꽂아야 한다면 현재 꽂아져있는 전기용품 중 가장 나중에 사용되는 전기용품을 빼준다.
4. 3번 로직이 이루어지는 수를 카운트하여 출력해준다.

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int[] seq = new int[k];
		List<Integer> list = new ArrayList<>();
		for(int i=0; i<k; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		
		Set<Integer> set = new HashSet<>();
		
		int cnt =0;
		for(int i=0; i<k; i++) {
			int num = list.get(i);
			if(set.contains(num)) continue;
			if(set.size()<n && set.add(num)) continue;
			
			int max = -1, idx =-1;
			for(int s : set) {
				int tmp=0;
				List<Integer> sub = list.subList(i+1, k);
				if(sub.contains(s)) {
					tmp = sub.indexOf(s)+1;
				}
				else {
					tmp = k-i-1;
				}
                
				if(tmp > max) {
					max = tmp;
					idx= s;
				}
			}
			set.remove(idx);
			set.add(num);
			cnt++;
		}
		
		System.out.println(cnt);
	}
}