[1700] 멀티탭 스케줄링 (python)

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

1700번: 멀티탭 스케줄링

 

• 문제에 대한 접근법

문제의 상황에서 볼 때 멀티탭을 꽃을때 최소의 꽃았다 뺐다를 반복하면서 전체 전기용품의 경우를 꽃는 것이다.

다음으로 미루어 봤을 때 경우를 나누어 조건에 맞춰 멀티탭을 꽃으면 된다.

멀티탭이 꽃을려 할 때 가장 먼저 멀티탭이 현재 비어있다면 순차적으로 꽃으면 되는 것이고, 만약 N개의 구멍에서 전부 꽃아져 있다면 다음 꽃을 전기용품이 이미 꽃혀있는지를 전제로 확인해야한다.

 

위의 조건이 만족이 안되었을 경우에는 하나를 빼고 해당 전기용품을 넣어야하는데 '어떤 것을 빼는것이 나중을 생각해 보았을 때 가장 효율적으로 뺄까?' 에 대해서 고민을 해야한다.

 

현재 꽃아야할 전기용품의 index부터 앞으로 꽃을 전기용품을 살펴보며 같은 전기용품이 있다면 다음 index를 각각 살펴 가장 큰 index값을 살핀다.

 

예를 들어보자

N = 3 , K = 9 인 상황에서 전기용품이 1 2 3 3 5 7 5 8 3 이라고 하자.

 

앞선 전제 조건에서 index가 2가 될때까지 1,2,3 이 순차적으로 꽃힐 것이다 .(index 시작은 0)

 

다음 index = 3 일 경우, 3은 이미 꽃혀있으므로 넘어간다.

 

index = 4일 경우 5가 꽃혀야 하는 상황이다. 1,2,3 이 이미 꽃혀있는 상황에서 1은 그 이후에 없으므로 index를 매우 큰 값으로 잡으며, 2 또한 높게 잡는다. 3은 맨 마지막인 index = 8로 인식이 되어 현 상황에서는 1,2의 위치 중 하나를 임의로 뽑고 그 자리에 5를 넣으면 된다.

작은 값인 1을 빼고 5를 넣는다고 가정하면 멀티탭은 현재 [ 5, 2, 3] 이 될 것이다.

 

index = 5라면 7이 나오게 된다. 해당 전기용품 또한 꽃으러 갈 때 5는 index=6에 해당되며, 3은 index = 8에 해당된다. 따라서 다음 전기용품 번호가 없는 2 자리에 7이 들어가게 된다. [5, 7, 3]

 

이후 동일한 알고리즘을 반복하여 기존에 있는 리스트 자리를 빼고 다음 자리에 들어갈 때 결과값을 증가시키면 될 것이다.

 

import sys

input = sys.stdin.readline

N, K = map(int,input().split())
use = list(map(int, input().split()))
result = 0
current = [] # 현재 꽃혀있는 멀티탭의 정보 저장

for i in range(K):
    # current 안에 이미 꽃혀있는게 있다면 넘어가야함
    if use[i] in current: 
        continue
    
    # current가 주어진 N의 길이보다 짧으면 use[i] 삽입
    if len(current) < N:
        current.append(use[i]) 
        continue
    
    compare_list = []
    for j in current:
        if j in use[i:] :
            compare_list.append(use[i:].index(j)) # 앞으로 use[i:] 에 똑같이 j 가 있다면 compare_list에 가장 최근의 index를 기입
        else:
            compare_list.append(1000)
    
    change_idx = compare_list.index(max(compare_list))
    current.remove(current[change_idx])
    current.append(use[i])
    result += 1

print(result)

• 깨달은 점

접근법은 알아도 앞에 전제하는 부분에 있어 정리하는데 오랜시간이 걸렸다.

구현의 아이디어도 물론 중요하지만 해당 아이디어를 코드로 말하는데 있어서 얼마나 표현이 명확한지에 따라 코드의 메모리가 결정되고 compact 하다는 것을 알았다.

 

그리디 알고리즘은 재밌지만 결국 이것도 명확하게 나의 것으로 표현하는 법은 익히고 정진해야한다.