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

문제

1700번: 멀티탭 스케줄링

---

풀이

어떤 플러그를 빼야 하는가에 대하여 Greedy하게 접근해야 했다.

a. 반례

처음에는 단순히 기기의 사용 횟수를 기준으로 스케줄링을 하였는데, 이 방법으로 접근하면 사용 순서에 따른 우선순위가 고려되지 않게 된다. 따라서 가장 마지막에 쓰일 기기 플러그부터 제거하는 스케줄링 방식으로 다시 접근하여 해결하였다.

3 14
1 4 3 2 5 4 3 2 5 3 4 2 3 4

2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3

 

b. 최종 풀이

1. 입력받은 data를 집합으로 형변환
2. 집합 내의 원소에 대하여, data에서 가장 먼저 등장하는 지점의 index 정보를 저장한 딕셔너리 생성 (usage)
3. 우선순위가 가장 낮은 순으로 정렬 (_usage)
    ※ 현 시점 이후(data[idx:])로, 다시 스케줄링하였을 때 가장 마지막으로 사용할 장치 순으로 정렬하는 것!

4. data에 대한 for문 수행
   a. 장치가 port에 꽂혀 있는 경우는 continue
   b. 장치가 port에 꽂혀 있지 않고, port에 자리가 남아 있는 경우
       -> 장치를 꽂는다
   c. 장치가 port에 꽂혀 있지 않지만, port에 자리가 남아 있지 않은 경우
      -> 우선순위가 가장 낮은 것 중 port에 존재하는 장치를 제거한 후 새로운 장치를 꽂고, answer += 1
   c. 우선순위 재정렬

n, k = map(int, input().split())
data = [x for x in map(int, input().split())]

  """
  data_set: 전기 용품의 이름을 저장한 set
  idx: 전기 용품 사용 순서 index
  usage: 전기 용품이 처음으로 사용되게 되는 순서 index를 저장한 dict
  _usage: 사용 우선 순위가 낮은(가장 먼저 제거할) 전기 용품 순으로 정렬한 list
  port: 멀티탭에서 플러그가 꽂힌 위치를 저장한 set
  """

data_set = set(data)
idx = 1
# 현 위치 이후부터 다시 사용하지 않을 전기 용품은 사용 순서를 최댓값(100)으로 설정하여, 최하위 우선순위를 부여
usage = {x: data[idx:].index(x) if x in data[idx:] else 100 for x in data_set}
_usage = [val[0] for val in sorted(usage.items(), key=lambda x:x[1], reverse=True)]

answer = 0
port = set()

for x in data:
    if x not in port and len(port) < n:
        port.add(x)
    elif x not in port and len(port) == n:
        for u in _usage:
            if u in port:
                port.remove(u)
                port.add(x)
                answer += 1
                break
    idx += 1
    usage = {x: data[idx:].index(x) if x in data[idx:] else 100 for x in data_set}
    _usage = [val[0] for val in sorted(usage.items(), key=lambda x: x[1], reverse=True)]

print(answer)