[백준/1700] 멀티탭 스케줄링 (Python)

Problem : 1700번: 멀티탭 스케줄링 (acmicpc.net)

1700번: 멀티탭 스케줄링

Difficulty : Gold 1

Status : Solved

Time : 00:23:16

 

---

 

 

문제 설명

 

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

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

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

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

 

 

입력 및 출력

 

입력

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

 

출력

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

 

입력 예시

2 7
2 3 2 3 1 2 7

 

출력 예시

2

 

 

---

 

 

풀이

 

그리디 알고리즘으로 풀 수 있는 문제. 그리디의 기준을 잡는 게 조금 헷갈렸었다. 처음에는 '지금 시점부터 남은 전기 용품의 빈도수'를 기준으로 알고리즘을 택했다. 즉 플러그를 뽑아야 할 상황에서는 이후 가장 빈도가 낮은 코드를 뽑는다. 하지만, 이런 경우 다음과 같은 반례가 생길 수 있다.

2 8
1 2 3 4 3 4 2 2

 

1. 먼저 콘센트에는 1, 2가 차례대로 들어간다.
2. 3을 넣을 시점에, 가장 빈도값이 낮은 1이 빠지므로 (2, 3)이 남는다. 플러그 교체 횟수는 1이다.
3. 4를 넣을 시점에, 가장 빈도값이 낮은 3이 빠지므로 (2, 4)가 남는다. 플러그 교체 횟수는 2이다.
4. 다시 3을 넣을 시점에, 가장 빈도값이 낮은 2가 빠지므로 (3, 4)가 남는다. 플러그 교체 횟수는 3이다.
5. 다시 4를 넣을 시점은 그대로 진행한다.
6. 다시 2를 넣을 시점에는 가장 빈도값이 낮은 3이 빠지므로 (2, 4)가 남는다. 플러그 교체 횟수는 4이다.
7. 마지막으로 2를 넣을 시점에는 그대로 진행한다.

정답은 4라고 생각할 수 있으나, 실제 정답값은 3이다.

이번에는 남은 전기 용품 리스트에서 가장 나중에 출현하는 코드를 뽑아보자. 즉 지금 시점부터 남은 전기 용품 중 가장 늦게 출현하는 원소를 기준으로 알고리즘을 택한다.

 

1. 먼저 콘센트에는 1, 2가 차례대로 들어간다.
2. 3을 넣을 시점에, 1은 더 이상 출현하지 않으므로 1이 빠지고 (2, 3)이 남는다. 플러그 교체 횟수는 1이다.
3. 4를 넣을 시점에, 2가 3보다 더 나중에 출현하므로 2를 뺀다. (3, 4)가 남고 플러그 교체 횟수는 2가 된다.
4. 다시 3을 넣을 시점 및 4를 넣을 시점은 그대로 진행한다.
5. 다시 2를 넣을 시점에는 더 이상 3, 4가 출현하지 않으므로 둘 중 하나를 빼도 상관이 없다. 플러그 교체 횟수는 3이다.
6. 마지막으로 2를 넣을 시점에는 그대로 진행한다.

이런 식으로, 빈도수보다는 출현 시기를 기준으로 풀이해야 정상적으로 동작함을 확인할 수 있다.

 

풀이 코드

N, K = map(int, input().split())
if N >= K :
  print(0)
  exit()

elec_list = list(map(int, input().split()))

plug = set()
cnt = 0

def find_latest(idx) :
  result = 0
  max_idx = -1
  for num in plug :
    try :
      num_idx = elec_list[idx:].index(num)
    except :
      num_idx = K
    if max_idx < num_idx :
      result, max_idx = num, num_idx
  
  return result
  
for idx, num in enumerate(elec_list) :
  plug.add(num)
  if len(plug) > N :
    cnt += 1
    latest_used = find_latest(idx)
    plug.discard(latest_used)

print(cnt)

풀이 완료!

 

P.S.

어째서 이런 식으로 동작하는 게 정답인가? 구현이 먼저었고 증명이 어려웠었는데, 답은 운영체제 기초 분야에서 얻을 수 있었다. 페이징 기법 중 가장 낮은 빈도 데이터를 우선적으로 교체하는 belady's min algorithm 기법이 해답이 되었다. 잘 생각해 보면 본 문제와 거의 대응되는 상황이라고 볼 수 있었다. Solved.ac 난이도 의견 부분에서 답을 구할 수 있었네... 오늘도 하나 더 배워간다.

 

그리고 생각해보니, plug in을 먼저 수행하고 그 다음에 바로 알고리즘으로 제거해버리는데, 이런 경우 반례가 발생할 수 있지 않을까? 싶다.