[백준/파이썬] 1700 : 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

문제 요약 : N개의 멀티탭 구멍을 가지고 K번 전기 용품을 사용하려고 한다. 플러그를 빼는 최소의 횟수를 구하여라.

예제 입력 1 :

2 7
2 3 2 3 1 2 7

예제 출력 1:

2

 

그리디 알고리즘!!!!

어느 전기 용품이 가장 나중에 사용되는지 확인하여 그 제품에게 우선 뽑힐 권리를 준다!

 

시도 )

처음에 그냥 가장 많이 사용할 전기 용품을 나중에 빼면 되지 않나? 라는 접근을 했다.

그러나, 가장 많이 사용하더라도 뒤에 몰려있으면, 앞에는 빼는게 더 나을 수 도 있다..!

 

2 9
1 2 3 1 2 3 1 2 3

 

이 예제에서 답이 4가 나와야하는데, 5가 나와서 잘못된 풀이임을 깨달았다.

# 멀티탭 스케줄링
N, K = map(int,input().split(' '))
use = list(map(int,input().split(' ')))

useDict = dict()

for i in use :
    if i in useDict :
        useDict[i] += 1
    else :
        useDict[i] = 1

code = []
for j in range(N):
    code.append(use[j])

answer = 0
for u in use[N-1:] :
    if u in code :
        continue
    
    if useDict.get(code[0]) >= useDict.get(code[1]) :
        code[1] = u
    else :
        code[0] = u
    useDict[u] -= 1
    answer += 1

print(answer)

 

📌 풀이 )

사실 하루종일 붙잡다가 힌트를 봐부렸다..ㅎㅎ

남은 사용 중에 가장 늦게 사용되는것을 뽑으면 된다!

K의 범위가 100이하였기 때문에, 다음에 사용되지 않는 전기용품은 다음에 가장 먼저 뽑힐 수 있도록 101값을 주었다.

 

저 우선순위 때문에 처음에 우선순위 큐를 이용하여 code에 번호와 다음 인덱스 번호를 같이 저장했는데, 그렇게 되면 코드에 이미 꽂혀있는지 확인하는 과정이 꼬이게 되어 그 부분에서 시간을 오래 잡아 먹었다.

아닐 땐 과감하게 다른 방법을 고안하는 것이 필요하다!!!!!

 

# 멀티탭 스케줄링
N, K = map(int,input().split(' '))
use = list(map(int,input().split(' ')))
code = []
answer = 0

for this in range(K):
    if use[this] in code :  # 코드에 이미 꽂혀져있음
        continue

    if len(code) < N :  # 코드 자리 남음
        code.append(use[this])
        continue

    priority = []
    for c in code:  # 꽂혀져 있는 코드들
        if c in use[this:]: # 다음에 또 이용해야한다면
            priority.append(use[this:].index(c))
        else:
            priority.append(101)
    target = priority.index(max(priority))
    code.remove(code[target])
    code.append(use[this])
    answer += 1

print(answer)