[BOJ 1700] 멀티탭 스케줄링

풀이

처음에 멀티탭 구멍 갯수만큼 먼저 전기제품을 꽂아준 후에 남아있는 전기제품들 중 사용빈도가 가장 높은 전기제품을 멀티탭에서 빼지않고, 나머지 꽂힌 전기제품들을 빼는 방식으로 접근하였다. 당연히 올바른 로직이 아니기 때문에 틀렸다. 문제를 푸는 로직은 아래와 같다.

1. (전기제품 사용 순서 리스트를 중심으로) 멀티탭에 동일한 전기제품이 꽂혀있을 경우 건너뛴다. (전기제품 빼지 않음)

2. 멀티탭에 빈자리가 있을 경우, 해당 빈자리에 전기제품을 꽂는다.

3. 멀티탭에 동일한 전기제품이 아니며 빈자리가 없을 경우, (이 경우를 생각하느라 힘들었다...)

   • 멀티탭에 꽂혀있는 제품들 중 이후에 꽂는 제품(전기제품 사용 순서 리스트)이 없을 때 멀티탭에 해당 제품(이후에 꽂을 일이 없는 제품)을 빼주고 탐색중인 전기제품을 꽂는다. --> 이후에 꽂을 일이 없는 제품을 빼주면 나중에 다시 플러그를 뺄 일이 없기 때문이다. (뽑는 횟수를 최소화할 수 있음)

   • 멀티탭에 꽂혀있는 제품들 중 가장 나중에 꽂는 제품을 찾는다. 즉, 멀티탭에 꽂혀있는 제품들 중 가장 나중에 꽂아야하는 전기제품을 뽑고 탐색중인 전기제품을 꽂는다. --> 뽑는 횟수를 최소화해야 하기 때문이다.

그리디 문제 + 구현 문제라고 생각한다. 구현하는데 많이 헤맨 문제이다.

코드

import sys

input = sys.stdin.readline
N, K = map(int, input().split())
products = list(map(int, input().split()))
multi_tab = [0] * N
ans = 0
change = maximum = 0

while products:
    product = products[0]
    # 멀티탭에 동일한 제품이 꽂혀있을 경우 -> skip
    if product in multi_tab:
        products.remove(product)    # 멀티탭에 꽂았으니 제품 사용 순서 리스트에서 삭제
        continue

    # 멀티탭에 빈자리가 있을 경우 -> 빈자리에 해당 제품 꽂는다.
    elif 0 in multi_tab:
        multi_tab[multi_tab.index(0)] = product
        products.remove(product)

    # 멀티탭에 빈자리가 없을 경우
    else:
        for mt in multi_tab:
            # 멀티탭에 꽂혀있는 제품 중 이후에 꽂는 제품이 없는 경우
            # 이후에 꽂는 제품이 없는 제품을 빼주고 탐색중인 제품을 꽂는다.
            if mt not in products:
                change = mt
                break

            # 멀티탭에 꽂혀있는 제품 중 가장 나중에 사용하는 제품을 고름.
            # -> 가장 나중에 사용하는 제품을 뽑고 탐색하고 있는 제품을 꽂는다.
            elif products.index(mt) > maximum:
                maximum = products.index(mt)
                change = mt

        multi_tab[multi_tab.index(change)] = product
        products.remove(product)
        maximum = 0
        ans += 1

print(ans)