[BOJ] 1700번 - 멀티탭 스케줄링

[BOJ] 1700번 - 멀티탭 스케줄링

 

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

1700번: 멀티탭 스케줄링

알고리즘

---

그리디 알고리즘 

멀티탭을 오랫동안 유지하고 싶음으로 가장 나중에 사용할것을 바꾸어주는게 좋다.

1. 멀티탭에 이미 있는 경우 -> PASS

2. 멀티탭에 빈자리가 있는 경우 -> 빈자리에 꼽는다.

3. 멀티탭에 있는것을 뺀 다음 새롭게 꼽는다.

4. 단 멀티탭에 있는 것을 빼기 위해서는 다음에 사용하지 않을 것이 우선순위

5. 다음에 사용된다면 가장 나중에 사용되는것을 뽑는다.

6. 매 전자기기 사용 시 1~5 반복

 

코드

---

#BOJ 1700번
import sys

n , m = map(int,input().split())
digital = list( map(int,input().split()) )
multitap = [0]*n
answer = 0

for index , data in enumerate(digital) :
    # 꼽혀있는 경우
    if data in multitap :
        continue
    # 멀티탭이 비어있는 경우
    if 0 in multitap :
        multitap[multitap.index(0)] = data
        continue

    # 빼야 하는 경우
    # 멀티탭에 있는 것중에서 가장 뒤에 나오거나 안나오는 애들
    target_index = -1*sys.maxsize
    check = False
    temp = digital[index:]
    for multitaps in multitap :
        if multitaps not in temp :
            multitap[multitap.index(multitaps)] = data
            check = True
            break
        else :
            target_index = max(temp.index(multitaps) , target_index )

    if target_index != -1*sys.maxsize and not check :
        multitap[multitap.index(temp[target_index])] = data
    answer += 1

print(answer)