[백준] 23843번 : 콘센트

23843번: 콘센트

23843번: 콘센트

📄 문제개요

• 전자 기기를 충전하려고 할때, 사용가능한 콘센트의 개수는 M개가 있고, 성능은 모두 동일하다.
• 전자기기들은 한번에 하나의 콘센트에서만 충전 가능하고, 충전에 필요한 시간은 2^k 형태이다.
• 광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간을 구하여라.

🤔 문제분석

• 충전시간이 가장 오래걸리는 전자기기부터 콘센트에 꽂는다.
• 충전시간이 다 끝나면 해당 전자기기를 빼고, 다음의 전자기기를 넣는다.
• 전자기기가 빠지는경우는, 현재 전자기기중에서 가장 충전시간이 작은 전자기기가 다음에 빠질 것이다.
• 따라서 가장 작은 전자기기를 기준으로 시간을 카운팅 한다.

📝 의사코드

1. 전자기기를 충전시간을 기준으로 내림차순 정렬한다.
2. 전자기기중 가장 충전시간이 짧은 시간을 구하기위하여 우선순위 큐를 사용한다.
3. 전자기기를 넣을 수 있으면 전자기기를 가장 오래걸리는 기기부터 콘센트에 넣는다.
4. 전자기기를 넣을 수 없다면 아래의 로직으로 전자기기를 빼고 넣는다.
   1. 충전시간이 가장 적은 시간을 기준으로 모든 전자기기의 시간을 줄인다.
   2. 충전시간이 0이된 전자기기는 큐에서 모조리 뺀다.
   3. 큐가 비었으니 전자기기를 넣는다.
5. 전자기기를 모두 순회한뒤, 남은 전자기기가 있다면 충전시간을 계산하며 빼낸다.

💻 코드

import heapq, sys
input = sys.stdin.readline
N, M = map(int, input().split())
devices = list(map(int, input().split()))
devices.sort(key=lambda x:-x)

queue = []
ans = 0
for device in devices:
    if M > len(queue):
        heapq.heappush(queue, device)
    else:
        time = queue[0]
        ans += time
        
        for i in range(len(queue)):
            queue[i] -= time
        
        while queue and queue[0] == 0:
            heapq.heappop(queue)
            
        heapq.heappush(queue, device)
    
while queue:
    time = queue[0]
    ans += time
    for i in range(len(queue)):
        queue[i] -= time
    
    while queue and queue[0] == 0:
        heapq.heappop(queue)
            
print(ans)

🎯 피드백 및 개선사항

• 현재의 알고리즘은 O(N*M)으로 M이 만약 증가하게된다면, 원하는 시간복잡도로 문제를 해결 할 수 없다.
• 아래의 문제는 O(N*Log(M))으로 문제를 해결 하였다.

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

• 큐를 일정 크기를 유지하면서 가장 작은 장치에, 가장 큰 장치를 넣어가며 업데이트한다.

import sys
import heapq
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split())
arr = list(map(int,input().split()))
max_heap = [0]*M
arr.sort(reverse=True)
for t in arr:
        last = heapq.heappop(max_heap)
        heapq.heappush(max_heap,last+t)
print(max(max_heap))