백준 20136 멀티탭 스케줄링 2 파이썬 풀이

난이도 : 플레티넘4

풀이일 : 2404092

https://www.acmicpc.net/problem/20136

20136번: 멀티탭 스케줄링 2

---

문제 캡쳐

---

아이디어

• 멀티탭에 빈 자리가 있다면, 현재 기기의 플러그를 연결하고, 현재 기기의 다음 사용 순서를 기록한다.
• 멀티탭에 빈 자리가 없다면 연결되어 있는 기기 중 다음 사용 순서가 가장 많이 남은 것을 제거하고, 현재 기기를 연결한 후, 현재 기기의 다음 사용 순서를 기록한다.

---

전체 풀이코드

import sys, heapq

N, K = map(int, sys.stdin.readline().split())
devices = list(map(int, sys.stdin.readline().split()))
order = [[] for _ in range(K + 1)]  # 사용 순서
count = 0  # 플러그 제거 횟수

for i in range(K):
    heapq.heappush(order[devices[i]], i)

docking = set()  # 현재 꽂혀있는 플러그
plugs = []  # 최대힙
for device in devices:
    heapq.heappop(order[device])  # 사용 표시
    # 디바이스 플러그가 연결되어 있지 않고, 연결된 플러그가 가득찬 경우
    if device not in docking and len(docking) == N:
        # 다음 사용 순서가 가장 늦은 플러그 제거 후 count + 1
        _, target = heapq.heappop(plugs)
        docking.remove(target)
        count += 1
    # 현재 사용할 디바이스의 플러그 연결
    docking.add(device)
    if order[device]:  # 현재 사용할 디바이스의 재사용 계획이 있을 경우
        heapq.heappush(plugs, [-order[device][0], device])
    else:  # 현재 사용할 디바이스의 재사용 계획이 없을 경우
        heapq.heappush(plugs, [-(K + 1), device])

print(count)

---

상세 설명

N, K = map(int, sys.stdin.readline().split())
devices = list(map(int, sys.stdin.readline().split()))
order = [[] for _ in range(K + 1)]  # 사용 순서
count = 0  # 플러그 제거 횟수

for i in range(K):
    heapq.heappush(order[devices[i]], i)

• devices : 전자기기들의 사용 순서
• order : 각 기기가 몇 번째로 사용되는지 저장할 이차원 배열이다.
• count : 플러그를 제거하는 횟수를 셀 변수이다.
• for 반복문 : devices 정보를 사용하여, order에 각 전자기기를 사용하는 순서를 기록해준다.
  • 유사 골드 문제에서는 heapq보다 list로 pop 해주는게 더 속도가 빨랐지만, N, K 제한이 100에서 500,000으로 늘어났기 때문에 heapq 자료구조를 이용해준다.

 

docking = set()  # 현재 연결된 디바이스
plugs = []  # 최대힙
for device in devices:
    heapq.heappop(order[device])  # 사용 표시
    # 디바이스 플러그가 연결되어 있지 않고, 연결된 플러그가 가득찬 경우
    if device not in docking and len(docking) == N:
        # 다음 사용 순서가 가장 늦은 플러그 제거 후 count + 1
        _, target = heapq.heappop(plugs)
        docking.remove(target)
        count += 1
    # 현재 사용할 디바이스의 플러그 연결
    docking.add(device)
    if order[device]:  # 현재 사용할 디바이스의 재사용 계획이 있을 경우
        heapq.heappush(plugs, [-order[device][0], device])
    else:  # 현재 사용할 디바이스의 재사용 계획이 없을 경우
        heapq.heappush(plugs, [-(K + 1), device])

print(count)

• docking : 현재 연결되어 있는 플러그 정보를 저장한다. 중복을 허용하지 않기 위해 set으로 관리해준다.
• plugs : 각 디바이스의 다음 사용 순서를 저장한다. 최대힙을 활용한다.
  • docking, plugs를 분리하지 않고 코드를 짤 경우, 현재 연결되어 있는 디바이스의 재사용 정보를 업데이트 하기가 어려워 분리하였다.
• for 반복문 : devices 안에 있는 각 기기들에 대해 반복문을 수행한다.
• heapq.heappop(order[device) : order의 device 번째 배열의 맨 앞 요소를 삭제해준다. 위에서 적은 것처럼 리스트를 사용해 pop을 하면 시간초과가 발생한다.
• if device not in docking and len(docking) == N : 현재 디바이스가 연결되어 있지 않고, 멀티탭의 모든 자리가 가득 차 있다면, 이미 꽃혀있는 플러그 중 제거할 것을 정한다. 
  • plugs 최대힙에서 맨 앞에 위치한 디바이스의 다음 사용 순서와 번호를 저장해 삭제한다.
  • 삭제 시, 플러그 제거 횟수를 + 1 해준다.
• docking.add(device) : 현재 사용할 디바이스를 연결한다.
  • 연결 후, 현재 디바이스의 재사용 계획이 있다면, plugs 힙큐에 [-다음사용 순서, 디바이스 번호] 정보를 추가한다.
  • 현재 디바이스의 재사용 계획이 없다면, plugs 힙큐에 [-최대순서 + 1, 디바이스 번호] 정보를 추가한다.
• 모든 디바이스에 대해 반복문이 끝난 후, 멀티탭에서 플러그를 제거한 횟수를 출력한다.

---

느낀점

• 플레티넘 문제를 처음 시도한 건 아니지만 처음 성공해봤다!!! 이거 되게 기분 좋네.
• 처음에는 그저께 풀었던 멀티탭 스케줄링 문제처럼 풀어서 시간초과가 발생했는데, 주어지는 N, K 조건들을 보고 시간안에 괜찮게 들어올 지 어림잡아 볼 수 있도록 찾아보고 공부해봐야지. 지금은 우선 틀려서 안되나보다 하고 추측하고 다르게 개선하고 있어서 아쉽다.