Baekjoon 1700. 멀티탭 스케줄링 / Python

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

 

• 입력 처리:
  • n은 멀티탭 구멍의 개수, k는 전기용품의 총 사용 횟수입니다.
  • arr는 전기용품의 사용 순서 리스트입니다.
• 멀티탭 관리:
  • now 리스트는 현재 멀티탭에 꽂혀 있는 전기용품을 저장합니다.
  • 전기용품을 순서대로 처리하면서, 이미 멀티탭에 꽂혀 있으면 넘어갑니다.
  • 빈 구멍이 있으면 현재 전기용품을 멀티탭에 꽂습니다.
  • 빈 구멍이 없으면 멀티탭에 꽂힌 전기용품 중 앞으로 가장 늦게 사용되거나 더 이상 사용되지 않는 전기용품을 찾아서 그 자리에 현재 전기용품을 꽂습니다.
• 결과 출력:
  • 최소 플러그를 뽑는 횟수를 출력합니다.

n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 결과값을 저장할 변수
res = 0
# 현재 멀티탭에 꽂혀 있는 전기용품을 저장할 리스트
now = []

# arr의 각 전기용품 사용 순서에 대해 반복
for idx in range(k):
    # 만약 현재 전기용품이 이미 멀티탭에 꽂혀 있으면 계속 진행
    if arr[idx] in now:
        continue
    
    # 멀티탭에 빈 구멍이 있으면 현재 전기용품을 꽂음
    if len(now) < n:
        now.append(arr[idx])
        continue
    
    # 빈 구멍이 없으면, 앞으로 사용될 전기용품 중 가장 늦게 사용되거나 사용되지 않는 전기용품을 찾음
    farthest_idx = -1
    item_to_unplug = -1
    for item in now:
        try:
            next_use = arr[idx+1:].index(item)
        except ValueError:
            next_use = k  # 전기용품이 앞으로 사용되지 않으면 매우 큰 값으로 설정
        if next_use > farthest_idx:
            farthest_idx = next_use
            item_to_unplug = item

    # 가장 늦게 사용되거나 사용되지 않는 전기용품을 멀티탭에서 빼고 새로운 전기용품을 꽂음
    now.remove(item_to_unplug)
    now.append(arr[idx])
    res += 1


print(res)