[PY] <!> 1700 : 멀티탭 스케줄링

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

핵심 아이디어에 try-except 코드가 필요할 지 누가 알았겠어.. 진짜 말이 안된다.
전체적인 구조는 일관성 있었다고 자신 할 수 있지만, 멀티탭에서 뭘 뽑아야 하느냐에 대해 우선순위를 고려해보라고 하면 내가 떠오르는건 이게 더 불릴 만한 횟수를 고려 한 것 뿐이다.

1. 입력 받을 때 counting sort 하듯 작동시킬 플러그에 대한 횟수 카운트를 해둔다.
2. 플러그에 대한 제한이 있을 때 1번에서 작성했던 리스트에서 우선순위를 정하고 뽑는 것을 수행한다.

이게 기존 아이디어였고, 2번에 대한 수행이 다소 문제가 있었다. 
이 문제에서 원하는 것은 그게 아니라, 진짜 이후 입력에 대해 적절히 뽑을 만한 걸 알아내야 하는 것이었다.

기존 아이디어로 작성된 내 코드 (틀림)

import sys
input = sys.stdin.readline

ableConnectCnt, processCnt = map(int, input().split())
callingCountList = [0] * (processCnt + 1)
ableConnectList = [0] * (ableConnectCnt)
processList = list(map(int, input().split()))[:processCnt]
connectedCnt = 0
plugChangedCnt = 0

for i in range(len(processList)):
    callingCountList[processList[i]] += 1

for i in range(len(processList)):
    if(processList[i] in ableConnectList):
        callingCountList[processList[i]] -= 1
        # 이미 멀티탭에 꽂혀 있는 경우엔 별다른 조치 없이 -1만 하면 된다.
    else:
        if(connectedCnt < ableConnectCnt):
            ableConnectList[connectedCnt] = processList[i]
            connectedCnt += 1
            # n개에 도달하면 여기는 들어올 수 없다
        else:
            remainTask = float('inf')
            mostLowRemain = 0
            for j in range(len(ableConnectList)):
                # 멀티탭에 꽂힌 것중에 남은 할 일이 최고로 적은 것을 찾기
                if(callingCountList[ableConnectList[j]] < remainTask):
                    mostLowRemain = j
                    remainTask = callingCountList[ableConnectList[j]]
            ableConnectList[mostLowRemain] = processList[i]
            callingCountList[processList[i]] -= 1
            plugChangedCnt += 1
            # 제일 적은 할 일이 남은 애를 지금 새로 수행해야하는 애로 대체

print(plugChangedCnt)

정답 코드

import sys
input = sys.stdin.readline

ableConnectCnt, processCnt = map(int, input().split())
processList = list(map(int, input().split()))
ableConnectList = []
plugChangedCnt = 0

for i in range(processCnt):
    # 이미 멀티탭에 꽂혀 있으면 다음으로
    if processList[i] in ableConnectList:
        continue

    # 빈 슬롯이 있으면 추가
    if len(ableConnectList) < ableConnectCnt:
        ableConnectList.append(processList[i])
    else:
        # 교체가 필요한 경우: 가장 늦게 호출되거나 호출되지 않을 장치 선택
        farthest = -1
        index_to_replace = -1
        for idx, device in enumerate(ableConnectList):
            try:
                next_use = processList[i+1:].index(device)
            except ValueError:
                # 앞으로 호출되지 않는 장치는 바로 교체
                next_use = float('inf')
            
            if next_use > farthest:
                farthest = next_use
                index_to_replace = idx

        # 교체 수행
        ableConnectList[index_to_replace] = processList[i]
        plugChangedCnt += 1

print(plugChangedCnt)