2022.02.14 [백준] (python 파이썬) 멀티탭 스케줄링

 

 

 

 

 

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

1700번: 멀티탭 스케줄링

 

---

풀이

총 3가지 경우를 먼저 생각해 볼 수 있다.

 

   1. 현재 꽂아야 할 용품이 멀티탭에 꽂혀 있는 경우

   2. 멀티탭에 빈자리가 있을 경우

   3. 멀티탭이 꽉 차있을 경우

 

 

이중 3번째의 경우 다시 2가지로 나누어 생각해 볼 수 있다.

 

     3.1 멀티탭에 꽂혀있는 용품 중, 앞으로 꽂아야 할 용품 리스트에 없는 경우

     3.2 만약 멀티탭에 꽂혀있는 용품들이 앞으로 모두 다시 꽂아야 할 경우

 

이렇게 보면 총 5가지로 볼 수 있다.

 

그러면 이 중 1, 2번은 멀티탭에서 용품을 뽑을 필요가 없기 때문에 cnt는 증가하지 않는다.

 

3.1번은 for문을 돌려 만약 멀티탭에 꽂혀있는 용품이 앞으로 꽂아야할 용품 리스트에 없다면

다시 꽂지 않아도 되기 때문에 해당 용품을 뽑은 후 현재 꽂아야 할 용품을 꽂는다.

이러면 1개를 뽑은 상황이기 때문에 cnt를 증가시켜준다.

 

3.2번은 꽂혀있는 용품이 모두 앞으로 꽂아야 할 리스트에 있으면 이 용품들을 언제 다시 꽂아야

하는지 확인 후 max값과 비교해서 크면 나중에 꽂아야 하는것이기 때문에 max에 대입해준다.

이렇게 for문이 모두 돌고 나면 가장 늦게 꽂아야 하는 용품을 뽑고 그 자리에 현재 꽂아야 하는 

용품을 꽂고 cnt를 증가시켜준다.

여기에서 가장 늦게 뽑아야하는 용품을 뽑지않고 다른 용품을 뽑으면 그 용품을 다시 꽂았다가 

또 뺄 경우가 생기기 때문이다.

     

n,k=map(int, input().split())
arr=list(map(int,input().split()))
multi=[0]*n
cnt=0
while arr:
    change=0
    max=0
 
    # 멀티탭에 현재 꽂아야하는 용품
    x=arr[0]
 
    #멀티탭에 x가 있으면 다시 꽂을 필요 없으니
    #arr에서 x 제거(횟수는 늘어나지않음)
    if x in multi:
        arr.remove(x)
 
    #멀티탭에 0이 있는 경우(0은 초기에 설정해놓은
    #값이기 때문에 0이면 용품이 꽂혀있지 않은 상황)
    #x를 멀티탭의 0이 있는 자리에 삽입
    #arr에서 x 제거
    elif 0 in multi:
        multi[multi.index(x)]=x
        arr.remove(x)
 
    else:
        #멀티탭이 꽉 차있는 경우
        for i in multi:
 
            #멀티탭에 꽂혀 있는 용품 i가 앞으로 꽂아야할
            #리스트에 없는 경우 change에 i를 대입
            #(i를 다시 꽂을 필요가 없기 때문에)
            if i not in arr:
                change=i
                break
 
            #멀티탭에 꽂혀있는 i가 앞으로 꽂아야할 리스트arr에
            #있는 경우, 리스트에 있는 i의 인덱스(위치)가 크면 
            #나중에 꽂아야 해서 멀티탭에 있는 모든 i를 비교 후 
            #가장 큰 i를 제거(나머지는 가장 큰 i보다 먼저 다시 
            #꽂아야 하므로)
            elif arr.index(i)>max:
                change=i
                max=arr.index(i)
        multi[multi.index(change)]=x
        arr.remove(x)
        cnt+=1
print(cnt)