[백준/Python] 1700번: 멀티탭 스케줄링

문제

 

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

---

Algorithm

그리디 알고리즘

cntK_list 에 각 전기용품마다 사용 순서를 따로 deque로 저장한다.
그리디하게 해결하기 위해,
1. 멀티탭에 플러그가 꽂혀 있고, 해당 전기용품이 꽂혀있는지
2. 그렇지않다면 멀티탭에 공간이 남아있는지
3. 그렇지 않다면 멀티탭을 정렬한 후, 하나를 뽑는 후 새로 꽂는다. 이 때, 남은 전기용품의  순서를 기준으로 정렬한다.

 

---

 

 

Code

from collections import deque
input = __import__('sys').stdin.readline

N, K = map(int, input().rstrip().split())
K_list = deque(list(map(int, input().rstrip().split())))
cntK_list = [[0, deque()] for i in range(K + 1)]
N_list = []
cnt_N = 0
ans = 0

for i in range(K) :
    cntK_list[K_list[i]][0] += 1
    cntK_list[K_list[i]][1].append(i)

for i in range(K) :
    if cnt_N > 0 and K_list[0] in N_list :
        if cntK_list[K_list[0]][1] :
            cntK_list[K_list[0]][1].popleft()
        K_list.popleft()
        continue
    if cnt_N < N :
        N_list.append(K_list[0])
        cnt_N += 1
        if cntK_list[K_list[0]][1] :
            cntK_list[K_list[0]][1].popleft()
        K_list.popleft()
        continue
    else :
        N_list.sort(key=lambda x: (cntK_list[x][1][0] if cntK_list[x][1] else float('inf')))
        ans += 1
        N_list[-1] = K_list[0]
        if cntK_list[K_list[0]][1] :
            cntK_list[K_list[0]][1].popleft()
        K_list.popleft()
        continue
print(ans)

 

느낀 점

lambda 함수를 이용해 sort를 진행할 때, 조금 까다로웠다. 삼항 연산자를 새롭게 공부하였다.
첫 시도에서는 전기용품의 사용 횟수도 신경 썼지만, 사실 이는 중요한 요소가 아니다. cntK_list[][0] 가 횟수인데, 사실 지워야 하지만 앞으로 이런 실수를 안하기 위해 기록용으로 남겨두었다.