백준(1700) - 멀티탭 스케줄링 Python

백준(1700) - 멀티탭 스케줄링

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

어떻게 풀어야할지 감은 잡았지만 생각보다 구현하는게 어려웠던 문제이다.

list = [1,2,3,4,5,6] 가 있을 때 3에 해당하는 값이 몇번째 인덱스인지 확인하는 방법을 알아야 한다.

ind = list.index(3) # 이 방법으로 값이 3에 해당하는 인덱스중 앞에서부터 가장가까운 인덱스값을 확인할 수 있다.

1. k가 자연수로 주어지므로 멀티탭은 0으로 n만큼 초기화시킨다.

2. k를 순차적으로 확인한다

   1. 멀티탭에 사용할제품이 이미 꽂혀있으면 스킵

   2. 멀티탭에 0이 있으면(빈 자리가 있다) 그 자리에 꽂는다

   3. 멀티탭에 빈 자리가 없다면 멀티탭에 꽂혀있는 것 중 어느것을 뺄지 고른다.

      1. 이후에 다시 사용하지 않는다면 그 자리에 꽂는다.

      2. 이후에 사용하게 된다면 가장 뒤늦게 사용하는 제품을 찾아서 그자리에 꽂는다.

         (이 경우에 결과값에 1을 증가시킨다.)

n, k = map(int, input().split())
objs = list(map(int, input().split()))
multi = [0] * n

cnt = 0
temp = 0
res = 0
for i in range(k):
    if objs[i] in multi:
        continue
    elif 0 in multi:
        multi[multi.index(0)] = objs[i]
    else:
        for m in multi:
            if m not in objs[i:]:
                temp = m
                break
            elif objs[i:].index(m) > cnt:
                cnt = objs[i:].index(m)
                temp = m
        multi[multi.index(temp)] = objs[i]
        temp =  0
        cnt = 0
        res += 1

print(res)