백준 1700 멀티탭 스케쥴링

멀티탭 스케쥴링(백준 1700)

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

가장 헷갈린 부분은 ‘그리디’를 어떻게 적용하냐 였다
처음에는 ‘가장 빈도수’가 낮은 코드를 제거하는 방식으로 생각하였으나
오답이 나왔기에,
아이디어를 찾아보니
‘가장 나중에 사용하는 코드’를 먼저 뽑는다는
방식을 보며
‘회의실’ 같은 ‘스케쥴링’ 문제에 대해서
‘끝나는 시간’이 가장 이른 녀석부터 처리하는 것이 ‘그리디’하다는 방식인 것 같다
(이 경우에서는, ‘뽑는다’는 의미인 듯 하다)

Code

import sys
from collections import OrderedDict

inp = sys.stdin.readline

holeCount, useCount = map(int,inp().split())

seq = list(map(int,inp().split()))

tap = dict()
answer = 0

# 가장 마지막에 사용되는 전기 기구를 뽑는다
# 다만, 안 사용되면 그 전기 기구를 뽑는다

for i in range(useCount):
    elect = seq[i]
    if elect in tap: # 이미 꽃여 있음
        continue

    if len(tap) < holeCount: # 빈칸 있음
        tap[elect] = 1
        continue
    
    # 빈 곳 없어서 가장 나중에 사용하는 녀석을 뽑는다
    key = -1 # 뽑을 dict key
    ind = 0  # 모두 key가 뒤쪽에 있을 때 가장 나중 녀석 체크용도

    for ele in tap: # 모든 tap 내부의 기기 검사
        tempInd = -1
        for j in range(i+1,useCount):
            electJ = seq[j]
            if electJ == ele: # 뽑을 녀석이다
                tempInd = j   # 위치 저장하고 break
                break
        if tempInd == -1: # 얘 뒤에서 안 쓰네?
            key = ele # 뽑을 녀석에 집어넣고 break 해준다
            break
        elif tempInd > ind: # 가장 뒤에 있는 녀석 새로 찾음
            ind = tempInd
            key = ele
    
    if key != -1:
        tap.pop(key)
    else:
        tap.popitem()

    tap[elect] = 1

    answer += 1

print(answer)

해결 아이디어

1. 상황을 3가지로 나누어 처리한다
   
   • 이미 해당 전자기기가 꽂혀 있음
   • 빈 공간이 있음
   • 빈 공간이 없음 (그리디 적용하여 뽑을 코드 선택)
2. 빈 공간이 없는 시점에서
   현재 탭에 꽂혀있는 녀석들 중에
   나중에 사용 안하거나, 가장 나중에 뽑히는 녀석을 찾는다
   
3. 제거 후, 삽입
   이 때, 제거 횟수가 올라간다
4. 반복문 종료 후, 제거 횟수 출력