백준 1700 멀티탭 스케줄링 Python 3

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

1700번: 멀티탭 스케줄링

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1700.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import Counter
input = sys.stdin.readline
N, K = map(int, input().split())
uses = list(map(int, input().split()))
counter = Counter(uses)
taps = list()
cnt = 0
for i in range(K):
    if uses[i] in taps:
        counter[uses[i]] -= 1
        continue
    if len(taps) < N:
        counter[uses[i]] -= 1
        taps.append(uses[i])
    #하나 뽑아야 하는 경우,
    else:
        for j in range(N):
            if counter[taps[j]] == 0:
                taps[j] = uses[i]
                counter[uses[i]] -= 1
                break
        else:
            idx = [-1, -1]
            for j in range(N):
                for k in range(i+1, K):
                    if taps[j] == uses[k]:
                        if idx[0] == -1 or idx[1] < k:
                            idx[0] = j
                            idx[1] = k
                        break
            taps[idx[0]] = uses[i]
            counter[uses[i]] -= 1
        cnt += 1
print(cnt)

---

풀이 과정

사용할 전기용품을 순서대로 탐색하면서 멀티탭에 이미 꽂혀있다면 그냥 사용하고, 멀티탭에 꽂혀 있지 않은 경우에는 두가지를 탐색한다.

1. 멀티탭에 자리가 있는 경우, 사용할 전기용품을 멀티탭에 꽂는다.

2. 멀티탭에 자리가 없는 경우, 뽑을 플러그를 선택한다.

   2-1. 앞으로 사용할 필요가 없는 전기용품의 플러그가 있다면, 해당 플러그를 뽑고 현재 사용할 전기용품을 꽂는다.

   2-2. 꽂혀있는 전기용품 중에서 더 나중에 사용되는 전기용품 플러그를 뽑고, 현재 사용할 전기용품을 꽂는다.

import sys
from collections import Counter
input = sys.stdin.readline
N, K = map(int, input().split())

#전기용품 사용을 담는 배열
uses = list(map(int, input().split()))

#counter[i] = 전기용품 i의 남은 사용 횟수
counter = Counter(uses)

#현재 멀티탭 상태, taps[i] = i번째 멀티탭에 꽂혀있는 전기용품
taps = list()

#플러그를 뽑는 횟수
cnt = 0

for i in range(K):
	#현재 사용할 전기용품이 이미 멀티탭에 꽂혀있는 경우,
    if uses[i] in taps:
    	#전기용품을 시용했으므로 전기용품 사용 횟수를 차감한다
        counter[uses[i]] -= 1
        continue
        
    #현재 사용할 전기 용품을 멀티탭에 새로 꽂을 수 있는 경우,
    if len(taps) < N:
    	#전기용품 사용 횟수를 차감하고, 멀티탭에 추가한다
        counter[uses[i]] -= 1
        taps.append(uses[i])
        
    #플러그를 하나 뽑고 현재 사용할 전기 용품을 멀티탭에 꽂아야 하는 경우,
    else:
    	#앞으로 사용하지 않을 전기 용품이 멀티탭에 꽂혀있는지 탐색한다
        for j in range(N):
        	#사용하지 않을 전기 용품이 꽂혀있는 경우, 해당 플러그를 뽑고 현재 사용할 전기 용품 플러그를 꽂는다
            if counter[taps[j]] == 0:
                taps[j] = uses[i]
                counter[uses[i]] -= 1
                break
        
        #앞으로 사용할 전기 용품만 멀티탭에 꽂혀 있는 경우, 나중에 사용되는 전기 용품 플러그를 뽑는다
        else:
        	#idx[0] = 멀티탭에서 뽑아야하는 플러그, idx[1] = 해당 전기 용품이 다시 사용될 순서
            idx = [-1, -1]
            
            #현재 멀티탭에 꽂혀있는 전기 용품 탐색
            for j in range(N):
            	#해당 전기용품이 나중에 언제 사용되는지 탐색
                for k in range(i+1, K):
                    if taps[j] == uses[k]:
                    	#더 나중에 사용되는 전기 용품이라면 해당 플러그를 뽑기 위해 idx 배열에 저장한다
                        if idx[0] == -1 or idx[1] < k:
                            idx[0] = j
                            idx[1] = k
                        break
            #가장 나중에 사용될 전기용품의 플러그를 뽑고 현재 사용할 전기용품을 플러그에 꽂는다
            taps[idx[0]] = uses[i]
            counter[uses[i]] -= 1
            
        cnt += 1
        
print(cnt)

#시간복잡도 = O(N*K^2) -> O(n), 공간복잡도 = O(n)