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

1700번: 멀티탭 스케줄링

1700번: 멀티탭 스케줄링

📄 문제개요

• 전기 기구가 있고, 멀티탭의 플러그 개수가 정해져 있을때, 모든 전기기구를 주어진 순서에따라서 멀티탭 플러그에 꼽아서 사용해야하는데, 뽑았다가 빼야하는 최소 개수를 구하여라.

🤔 문제분석

• 그리디 문제로 여러가지를 처음에 생각해보았고, 아이디어가 떠올리지 않아서, 정답을 찾아보았습니다.
• 전기기구를 뽑을때 출연빈도가 낮아야 하는 전기기구를 뽑아야한다.

1. 가장 출연빈도가 높은 순으로 뽑는다.
2. 현재 연결해야하는 전기기구부터, 연결해야하는 멀티탭의 콘센트 수 까지의 전기기구 까지를 보아, 그중에 없는 전기기구를 뽑는다.

📝 의사코드

1. 콘센트에 전기기구가 하나라도 비어있다면 전기기구를 연결한다.
2. 콘센트에 전기기구가 꽉찼다면 전기기구를 하나 빼, 자기자신을 연결한다.
   1. 전기기구를 하나 빼는 방법은 연결된 콘센트중에서 가장 나중에 연결될 전기기구를 찾는다.
3. 전기 기구를 빼고 연결할때 카운팅을 한다.
4. 카운팅을 출력한다.

💻 코드

import sys
input = sys.stdin.readline

N, K  = map(int, input().split())
products = list(map(int, input().split()))

multi_tap = set()
ans = 0
for i in range(len(products)):
    if products[i] in multi_tap: # 이미 물품이 멀티탭에 있는경우
        continue
    
    if len(multi_tap) == N: # 멀티탭의 수가 꽉찬경우 (하나를빼서 현재 물품을 꽂아야한다.)
        max_idx = -1
        del_product = 101
        for p in multi_tap:
            try:
                idx = products[i:].index(p) # 현재위치로부터 가장 멀리있는 인덱스 찾기 ( 가장 나중에 장착될 전기용품 )
            except:
                # 제일 첫번째꺼가 골라짐.
                idx = K
            if max_idx < idx:
                del_product = p
                max_idx = idx

        ans += 1
        multi_tap.discard(del_product)

    multi_tap.add(products[i])

print(ans)

🎯 피드백 및 개선사항

• 해당 문제를 시간안에 풀지 못하였고, 어떤 아이디어가 있을까 인터넷에 검색해보았습니다.
• 운영체제 페이징 스케줄링 알고리즘 중 LRU 라는 알고리즘이 위의 문제의 해결 방안법과 비슷합니다.

페이징 스케줄링 으로 콘센트에 연결된 전기기구 중에서 가장 나중에 연결될 전기기구를 지금 당장 뺀다. 운영체제에서의 페이징 교체 알고리즘으로, LRU ( Least Recently Used ) 알고리즘으로, 가장 오랫동안 참조되지 않은 페이지를 교체 대상으로 선택한다.

❓다른사람은 어떻게 풀었을까?

• 모두 비슷한 방법으로 해결 하였습니다.

n, k = map(int,input().split())
arr = list(map(int,input().split()))
plug = []
c = 0

for i in range(k):
    if arr[i] in plug: 
        continue
    if len(plug)<n: 
        plug.append(arr[i])
        continue

    idxs = []
    for j in range(n):
        try:
            idxs.append(arr[i:].index(plug[j]))
        except:
            idxs.append(101)
    plug[idxs.index(max(idxs))] = arr[i]
    c += 1

print(c)