백준 1700번 python 풀이 - 잃어버린 괄호

문제 링크

1700번

해결책

import sys

INF = 999999

N, K = map(int, sys.stdin.readline().split())

use_order = list(map(int, sys.stdin.readline().split()))

use_timing = [[] for i in range(K + 1)]

for i in range(len(use_order)):
    use_timing[use_order[i]].append(i)
for i in range(len(use_timing)):
    use_timing[i].append(INF)

using_elec = []
cnt = 0


for i in range(len(use_order)):
    elec = next((elec for elec in using_elec if use_order[i] == elec[0]), None)
    if elec:
        use_timing[use_order[i]].remove(i)
        using_elec.remove(elec)
        using_elec.append((elec[0], use_timing[use_order[i]][0]))

    elif len(using_elec) < N:
        use_timing[use_order[i]].remove(i)
        using_elec.append((use_order[i], use_timing[use_order[i]][0]))

    else:
        using_elec.pop(-1)
        cnt += 1
        use_timing[use_order[i]].remove(i)
        using_elec.append((use_order[i], use_timing[use_order[i]][0]))

    for idx in range(len(using_elec)):
        elec, order = using_elec[idx]
        if order <= i:
            using_elec[idx] = (elec, INF)

    using_elec.sort(key=lambda x: x[1])

print(cnt)

주석으로 달 설명

그리디, 조금 고생했던 문제. 사실 아이디어로 고생하지 않았고, 무결성 정답을 찾는 과정에서 조금 애를 먹었다. 예제는 옳게 나왔었지만, 그 이후에 반례를 찾는 과정에서 시간을 많이 소모했던것 같다.

아이디어는 다음과 같다. 각 배열로, N번의 전자기기가 몇번째 인덱스에서 사용되는지를 정리한 뒤에, 이를 지속적으로 교체해주며, 멀티탭에서 빼야 할때는 이중 가장 이른 재사용이 늦은 것을 교체한다.

이로써 완!