[Algorithm][Python] 백준(BOJ) 1700 멀티탭 스케줄링 (Gold 1)

[문제]

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

---

🛠 문제점

문제 보고 생각했을 때,

1. 멀티탭에 있으면 패스
2. 멀티탭이 비어있으면 채우기
3. 멀티탭에 없고, 가득 찬 경우 새로 갈아 끼우기
   • 이후 전기제품 리스트에서 개수가 적은 걸 빼기 (문제점)

로 생각했다.

😭 문제가 되는 경우 : 바로 뒤에 같은 전기제품인데, 개수가 적어서 빠지게 되는 경우!!

❗️ 풀이법

위의 1, 2번은 동일하고 3번을 수정하면 된다!

• 해당 이후에 해당 전기제품이 나오지 않는 경우 제거
• 이후 전기제품 리스트에서 가장 뒤에 나오는 것 제거

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

multi = []
result = 0

for i in range(k):
    # 멀티탭에 꽂혀 있는 경우
    if elec[i] in multi:
        continue
    
    # 멀티탭이 비어 있는 경우
    if len(multi) < n:
        multi.append(elec[i])
        continue
    
    # 멀티탭 빼야할 경우

    change_plug = 0
    far_idx = 0

    for plug in multi:
        ## 이후에 안나올 경우
        if plug not in elec[i:]:
            change_plug = plug
            break
        
        # 가장 멀리있는 플러그 찾기
        if elec[i:].index(plug) > far_idx:
            far_idx = elec[i:].index(plug)
            change_plug = plug

    multi[multi.index(change_plug)] = elec[i]
    result += 1
    
print(result)