콘센트 23843 python

23843번: 콘센트

 

두가지 방식으로 풀었다.

# 예제 입력
# N M
5 2 
# arr
1 4 4 8 1

# 예제 출력
# 9

5 2
1 4 4 8 1
count :  1
before => arr :  [1, 1, 4, 4, 8]  / taskList :  []
after => arr :  [1, 1, 4]  / taskList :  [3, 7]

count :  2
before => arr :  [1, 1, 4]  / taskList :  [3, 7]
after => arr :  [1, 1, 4]  / taskList :  [2, 6]

count :  3
before => arr :  [1, 1, 4]  / taskList :  [2, 6]
after => arr :  [1, 1, 4]  / taskList :  [1, 5]

count :  4
before => arr :  [1, 1, 4]  / taskList :  [1, 5]
after => arr :  [1, 1, 4]  / taskList :  [4]

count :  5
before => arr :  [1, 1, 4]  / taskList :  [4]
after => arr :  [1, 1]  / taskList :  [3, 3]

count :  6
before => arr :  [1, 1]  / taskList :  [3, 3]
after => arr :  [1, 1]  / taskList :  [2, 2]

count :  7
before => arr :  [1, 1]  / taskList :  [2, 2]
after => arr :  [1, 1]  / taskList :  [1, 1]

count :  8
before => arr :  [1, 1]  / taskList :  [1, 1]
after => arr :  [1, 1]  / taskList :  []

count :  9
before => arr :  [1, 1]  / taskList :  []
after => arr :  []  / taskList :  []

9

import sys
import heapq

input = sys.stdin.readline
N, M = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))

# 정렬
arr.sort()

# arr를 우선순위큐로 바꿔준다
heapq.heapify(arr)

def solution():
    count = 0
    taskList = []
    while len(arr) > 0 or len(taskList) > 0:
        count += 1
        
        #arr가 비어있지 않고 taskList가 M보다 작으면 while
        while arr and len(taskList) < M:
        	# 정렬된 arr 에서 큰 수부터 빼서 taskList에 heappush()
            heapq.heappush(taskList, arr.pop())
            
        # taskList 전체에 -1을 한다.
        for i in range(len(taskList)):
            taskList[i] -= 1
            
        # 우선순위 큐인 taskList에 제일 작은수가 0이 아닐때까지 heappop() 을 한다.
        while len(taskList) > 0 and taskList[0] == 0:
            heapq.heappop(taskList)
    return count


result = solution()
print(result)