[백준] 1700번 : 멀티탭 스케줄링

안녕하세요. 매일공부하는 개발자 빅광스입니다. 저번주는 다이나믹 프로그래밍 문제를 풀어보았는데요, 이번주는 그리디 알고리즘 문제를 풀어보려고 합니다.

 

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

1700번: 멀티탭 스케줄링

오늘의 문제는 멀티탭 스케줄링 문제입니다. 문제의 내용은 위의 사이트에서 참고하시고 오세요.

 

저는 이 문제를 풀때 여러가지 테스트 케이스를 생각하면서 공책에 써가면서 최적해를 구하는 과정을 생각해보았습니다.

 

1) 현재 콘센트에 현재 넣으려는 아이템의 큐 안에 아이템이 없는경우 그 아이템을 우선적으로 현재 콘센트에서 뺀다.

2) 현재 콘센트에 현재 넣으려는 아이템이 모두 있는경우 큐에서 가장 멀리 뽑히게 될 아이템을 현재 콘센트에서 뺀다.

 

저는 이 두가지 방법을 가지고 아래의 코드를 작성하였습니다.

 

N, K = map(int, input().split())
useorder = list(map(int, input().split())) # 콘센트에 꽂아야 하는 아이템 리스트들

multitap = [] # 멀티탭
plugoff = 0
for _ in range(len(useorder)):
    item = useorder.pop(0)
    mincount = int(10e9)
    idx = 0
    
    if item in multitap: # 이미 콘센트에 꽂혀있는경우
        continue
    
    if len(multitap) == N: # 멀티텝이 꽉찬경우 콘센트에있는 하나의 아이템을 뽑아야한다.
        # 콘센트에 꽂혀있는 아이템중에 꽂을 리스트에 없는 아이템을 찾는다.
        concentidx = 0
        maxindex = 0
        for i in range(len(multitap)):
            
            if not multitap[i] in useorder:
                multitap.pop(i) # 리스트에 없는경우 아이템을 pop하고 break 한다.
                plugoff += 1
                break
            else :
                cost = useorder.index(multitap[i])
                if cost > maxindex: # 제일 멀리있는 아이템 index를 구한다.
                    maxindex = cost
                    concentidx = i
            
    
    if len(multitap) == N: # 리스트에 콘센트들이 다 있다면.
        multitap.pop(concentidx)
        plugoff += 1

    multitap.append(item)
        
print(plugoff)