BOJ 1092 배
접근 방법
제일 무거운 박스들부터 제거해야 더 약한 크레인도 제거할 기회가 생겨 최대한 빨리 옮길 수 있다. 즉, 각 크레인이 들 수 있는 가장 무거운 박스들을 제거해야 최소한의 시간 안에 다 제거할 수 있다. $\rightarrow$ Greedy algorithm인 것을 눈치챌 수 있다.
시간 초과 접근 방법
Greedy인 것을 안 상태로 각 크레인 별로 들 수 있는 가장 무거운 박스들을 제거하기 위해 각 크레인이 제거할 수 있는 모든 박스들을 우선순위 큐에 넣은 후, 마지막에 우선순위 큐에서 pop한 박스를 제거하였다. $\rightarrow$ 매번 우선순위 큐를 형성하게 되어 $\text{시간} \times \text{크레인 수} \times \text{박스 종류} \times \text{박스 종류 log 박스종류})$ 시간 복잡도를 갖게 된다.
이것을 해결하기 위해 어렵게 우선순위 큐를 사용하는 것이 아니라 그냥 계속 iterate하면서 각 크레인이 들 수 있는 가장 무거운 박스 무게를 구했다가 그 무게에 해당되는 박스를 제거하였다. $\rightarrow$ 모든 크레인에 대해 매번 모든 박스들을 조회하기 때문에 $\text{시간} \times \text{크레인 수} \times \text{박스 종류}$의 시간 복잡도를 갖게 된다.
정답인 접근 방법
가장 강한 크레인부터 가장 무거운 박스들을 옮길 수 있는지 확인하기 위해 크레인이 옮길 수 있는 한도와 박스 무게들을 내림차순으로 정렬하였다. 그래서 가장 강한 크레인이 가장 무거운 박스들을 들 수 있는지 보고 바로 iteration이 끝나도록 하였다. 그리고 각 크레인이 전에 옮긴 박스 위치들을 저장하여 이전 박스들은 보지 않아도 되도록 하여 시간 복잡도를 최적화하였다.
처음 생각한 코드 (1)
import sys
import heapq
input = sys.stdin.readline
n = int(input())
limits = list(map(int, input().split()))
m = int(input())
weights = list(map(int, input().split()))
"""
박스가 없어질 때까지 반복
이때 제거하는 것을 최대한 효율적으로 해야 최소 시간을 구할 수 있다.
각자 제거할 수 있는 최대한 무거운 무게를 계속 제거해야함. 제일 쎈 크래인이 제일 무거운 것을 들어줘야함
"""
left = dict()
for w in weights:
if w in left:
left[w]+=1
else:
left[w]=1
prev_removed = m
removed = m
total_time = 0
#50*10000*(10000 log 10000) -> 시간 초과
while True:
if removed <= 0:
print(total_time)
break
for limit in limits:
max_weight = 0
for weight in left.keys():
# 각 크레인이 제거 가능한 weight들 구하기
if left[weight]>0 and weight <= limit:
if max_weight < weight:
max_weight = weight
if max_weight != 0:
left[max_weight]-=1
#시간 복잡도 줄이기 위해 더 이상 없는 박스들은 제거하였다.
if left[max_weight] == 0:
left.pop(max_weight)
prev_removed = removed
removed -= 1
#박스 남아있는데 한 번의 iteration에서 제거된 적이 없다면 더 제거할 수 없는것
if removed == prev_removed and removed != 0:
print(-1)
break
total_time +=1
보석 찾기 문제 1202번처럼 우선순위 큐를 사용해본 방법
얘는 pop 할 때마다 최적인 애가 안 나오기 때문에 이렇게 풀면 안된다!
보석찾기 문제랑은 다름
문제 조건 상 가장 힘쎈 crane부터 가장 무거운 box들을 들어야 하기 때문에 q에는 무거운 box들도 들어감
따라서 q에 있는 애들 중에서 heapq.pop에 의해 나온 가장 무게가 높은 애는 나중에 약한 crane에 의해서 못 뽑힐 수도 있다 -> 이러면 greedy처럼 풀 수 없음
import sys
import heapq
input = sys.stdin.readline
n = int(input())
limits = list(map(int, input().split()))
m = int(input())
weights = list(map(int, input().split()))
"""
박스가 없어질 때까지 반복
이때 제거하는 것을 최대한 효율적으로 해야 최소 시간을 구할 수 있다.
각자 제거할 수 있는 최대한 무거운 무게를 계속 제거해야함. 제일 쎈 크래인이 제일 무거운 것을 들어줘야함
"""
limits.sort()
weights.sort()
left = dict()
for w in weights:
if w in left:
left[w]+=1
else:
left[w]=1
prev_removed = m
removed = m
total_time = 0
q = []
while removed>0:
for limit in limits:
for weight in left.keys():
# 각 크레인이 제거 가능한 weight들 구하기
if left[weight]>0 and weight <= limit:
heapq.heappush(q, -weight)
if q:
remove = -1 * heapq.heappop(q)
if limit >= remove:
#print(f"{limit} removed {remove}")
left[remove]-=1
removed -= 1
total_time +=1
print(total_time)
정답 코드
import sys
import heapq
input = sys.stdin.readline
n = int(input())
limits = list(map(int, input().split()))
m = int(input())
weights = list(map(int, input().split()))
"""
박스가 없어질 때까지 반복
이때 제거하는 것을 최대한 효율적으로 해야 최소 시간을 구할 수 있다.
각자 제거할 수 있는 최대한 무거운 무게를 계속 제거해야함. 제일 쎈 크래인이 제일 무거운 것을 들어줘야함
"""
limits.sort(reverse=True)
weights.sort(reverse=True)
if limits[0] < weights[0]:
print(-1)
sys.exit()
positions = [0]*(n)
left = dict()
for w in weights:
if w in left:
left[w]+=1
else:
left[w]=1
total_time = 0
removed_boxes = 0
while removed_boxes < m:
for i in range(n):
while positions[i] < m:
#각 크레인이 이전에 제거한 박스 위치에서 시작해서 아직 제거가 안 된 박스들 중에 가장 무거운 것을 제거
if weights[positions[i]] <= limits[i] and left[weights[positions[i]]]>0:
left[weights[positions[i]]] -= 1
positions[i]+=1
removed_boxes +=1
break
#그 위치의 박스가 이미 제거되었다면, 더 가벼운 박스들은 제거 가능한지 본다.
positions[i]+=1
total_time += 1
print(total_time)