멀티탭 스케줄링 ( 1700 번 )

1700번: 멀티탭 스케줄링

 

---

🧠 알고리즘

• 시뮬레이션(Simulation) + 최적 페이지 교체 알고리즘 (Belady’s Optimal Page Replacement)

 

✔️ 동작 방식

문제 핵심 아이디어
멀티탭에 여러 기기를 순서대로 꽂아야 할 때,
현재 꽂혀 있는 기기 중 가장 나중에 다시 사용되거나 아예 다시 사용되지 않는 기기를 빼는 것이 교체 최소화의 최적해가 된다.

즉, 앞으로 가장 늦게 사용할 기기를 교체하는 "최적 교체 알고리즘"을 시뮬레이션으로 구현한다.

 

주요 로직 요약

1. 입력 처리
   • slot: 멀티탭 구멍 개수
   • k_list: 사용 순서를 담은 deque
   • Counter로 남은 사용 횟수를 관리 (now_value)
2. 초기 세팅
   • 멀티탭이 다 찰 때까지 순서대로 꽂음
   • 꽂을 때마다 해당 기기의 남은 사용 횟수를 감소 (_cr_now_value)
3. 시뮬레이션 진행
   • 다음 기기를 확인
     1. 이미 꽂혀 있으면 패스
     2. 비어 있지 않으면 교체 필요
        → _cr_long_term() 함수로 가장 나중에 사용될 기기 탐색
        → 해당 기기를 제거하고 새 기기 꽂기
        → 교체 횟수(answer) +1
4. 결과 출력
   • 총 교체 횟수 출력

---

 

🧾 코드

import sys
from collections import deque, Counter

def _cr_now_value(now_num, now_dict):
    now_dict[now_num] -= 1
    
    if now_dict[now_num] == 0:
        now_dict.pop(now_num)

    return now_dict


def _cr_long_term(now_slot, k_list, now_value):
    number, idx = -1, -1
    for i in now_slot:
        if i not in now_value: # 앞으로 사용할일 없으면 걍 빼!!
            return i

        now_idx = k_list.index(i)
        if now_idx > idx:
            number, idx = i, now_idx

    return number
    

def _main(slot, k, k_list):
    answer = 0
    now_value = Counter(k_list)
    now_slot = set()

    # 초기값 셋팅
    while len(now_slot) < slot and k_list:
        q = k_list.popleft()
        now_slot.add(q)
        now_value = _cr_now_value(q, now_value)

    """
        1) 이미 슬롯에 있으면 continue
        2) 슬롯 교체 해야되면.. 누굴빼야 최적일까..
            - 최적 교체 알고리즘 -
            앞으로 가장 늦게 사용할 번호 교체
    """
    while k_list:
        q = k_list.popleft()
        now_value = _cr_now_value(q, now_value)
        
        if q not in now_slot:
            long_term = _cr_long_term(now_slot, k_list, now_value)
            now_slot.remove(long_term)
            now_slot.add(q)
            answer += 1

    return answer
    

slot, k = map(int, sys.stdin.readline().rstrip().split())
k_list = deque(list(map(int, sys.stdin.readline().rstrip().split())))

print(_main(slot, k, k_list))

---

 

⏱️ 시간 복잡도

for i in now_slot : 슬롯을 순회하며 ( 선형 시간 복잡도 )
	now_idx = k_list.index(i) : 현재 슬롯 인덱스 확인 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )