[백준/Python] 1700번 - 멀티탭 스케줄링

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split()) # n: 플러그 개수
usage = list(map(int, input().split()))

plug = usage[:1] # 앞 두개가 모두 같은 숫자일 수 있으므로 1개만 꽂아넣기
usage = deque(usage[1:])
result = 0

while usage:
  i = usage.popleft()
  # 이미 꽂혀있을 경우
  if i in plug:
    continue
    
  # 플러그 자리가 남았을 경우
  if len(plug) < n:
    plug.append(i)
    continue
  
  # 꽂혀있는 것들 중 뽑을 것 고르기(plug index)
  t = -1
  for p in range(len(plug)):
    # 더 이상 사용안하는 기기
    if plug[p] not in usage:
      t = p
      break
    # 사용은 하지만 사용 순서가 가장 멀리 있는 것(횟수가 얼마나 남았는지는 상관 없음)
    if t == -1:
      t = p
    else:
      t = t if usage.index(plug[t]) > usage.index(plug[p]) else p # 여기서 일치하는 값을 못찾으면 valueError 발생

  plug[t] = i
  result += 1

print(result)

그리디 알고리즘 문제이다.

bfs로 풀 수 있을까 고민하다가 n과 t의 범위가 최대 100인데 모든 경우의 수를 살펴보려면 100^100이므로 포기했다.(물론 조건 추가하면 경우의 수가 훨씬 줄어들테지만 아무튼!)

 

아무튼 차근차근 사용순서를 보고, 그때 그때 뽑을 플러그를 판단하는 방법 밖에 없다고 판단해서 아래와 같은 로직을 세웠다.

1. 사용순서를 순회한다
2. 이미 플러그가 꽂혀있거나, 플러그에 자리가 남아있을 경우, "뽑을 플러그 판단" 로직을 갈 필요 없이 continue
3. 뽑을 플러스는 더이상 사용을 안하거나, 사용 순서가 가장 멀리있는 순으로 뽑는다
(사용 횟수는 관계없다. 횟수가 아무리 많더라도 사용 순서가 가까이에 있는 전기 용품을 위해 플러그를 교체해야 하므로 횟수보다는 거리가 주요 지표다)

당연히, 3번 구현이 조금 까다로웠다.

index를 사용해야 했는데, deque의 index 메서드의 경우, 일치하는 값을 못찾으면 valueError를 반환하는 사실을 몰랐기 때문이다.

덕분에 답을 코앞에 두고 한참 해맸다

 

p의 경우는 위에서 usage 안에 있는지 확인하므로, valueError가 발행하는 원인은 t 때문이다.

처음에 t=0으로 초기화 해줬는데, plug[t] 값이 usage에 존재하지 않는 경우가 있었던 모양이다.

따라서 t=-1로 초기화해주고, usage 안에 있는지 확인한 이후 t의 초기값을(t=-1인 경우) p로 초기화시켜줬다.

 

그랬더니 성공적으로 해결할 수 있었다!

 

시간 복잡도

멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)

전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)

전기용품의 이름이 K 이하의 자연수

 

while문: O(K)

nested for문: O(N)

=>O(N*K) <= O(10000)

 

다른 사람 풀이

- t를 plug의 index로 두지 않고, plug 값(전기용품 번호)로 두고 마지막에 plug 교체할 때 plug의 index를 쓰면 valueError가 생길 일이 전혀 없다.