백준 1700번 - 멀티탭 스케줄링

멀티탭 스케줄링 문제 바로 가기

풀이 날짜: 2026-01-29

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n,k = map(int, input().split())
kind = list(map(int, input().split()))
answer = []
count = 0

for idx in range(k):
    now = kind[idx]

    if now in answer:
        continue
    elif len(answer) < n:
        answer.append(now)
        continue

    next_use = []
    for pulgged in answer:
        if pulgged in kind[idx+1:]:
            next_use.append(kind[idx+1:].index(pulgged))
        else:
            next_use.append(float('inf'))

    remove_index = next_use.index(max(next_use))

    answer.pop(remove_index)
    answer.append(now)
    count += 1

print(count)

문제 핵심 - 가장 막혔던 부분

멀티탭이 꽉 찼을 때 어떤 기기를 뽑아야 하는지는 이해했지만, 실제 코드에서 next_use를 만드는 과정이 가장 헷갈렸다. 특히 “다음에 언제 다시 쓰이는지”를 숫자로 표현한다는 개념이 바로 떠오르지 않아, 코드 한 줄이 왜 필요한지 납득하기까지 시간이 걸렸다.

미래 사용 시점을 수치화한다

이 문제의 핵심은 현재 상황이 아니라 앞으로의 사용 순서를 기준으로 판단하는 것이다. 현재 꽂혀 있는 각 기기에 대해, 이후 사용 목록에서 몇 번째에 다시 등장하는지를 숫자로 표현하면 비교가 가능해진다. 이 숫자가 바로 next_use에 저장되는 값이다.

kind[idx+1:]가 의미하는 것

kind[idx+1:]는 현재 시점 이후에 사용할 기기들의 목록이다. 이 리스트를 기준으로 “지금 꽂혀 있는 기기가 앞으로 다시 등장하는지, 등장한다면 언제인지”를 판단하게 된다. 즉, 과거는 완전히 무시하고 미래만을 바라보는 기준선이 된다.[-flen:]은 스택의 맨 뒤에서 폭발 문자열 길이만큼만 잘라낸 부분을 의미한다. 이 부분을 문자열로 변환하여 폭발 문자열과 비교함으로써, “방금 추가된 문자로 인해 폭발이 발생했는지”를 정확하게 판단할 수 있다.

index()로 다음 사용 위치 구하기

현재 꽂힌 기기가 미래 목록에 있다면, index()를 통해 처음 등장하는 위치를 구한다. 이 값이 작을수록 곧 다시 사용된다는 의미이고, 값이 클수록 더 나중에 사용된다는 뜻이 된다.

다시 사용되지 않을 경우

미래 목록에 아예 등장하지 않는 기기는, 지금 제거해도 전혀 불이익이 없다. 이를 코드에서는 float(‘inf’)로 표현했고, 비교할 때 가장 큰 값이 되도록 만들었다.

next_use 리스트

next_use는 현재 멀티탭에 꽂혀 있는 기기들과 동일한 순서를 유지하면서, 각 기기의 “다음 사용 시점”을 숫자로 저장한 리스트다. 이 중 가장 큰 값을 가진 기기가 가장 늦게 쓰이거나 다시 쓰이지 않는 기기이므로, 제거 대상으로 선택된다.

Vienna sausage