배 ( 1092 번 )

1092번: 배

 

---

🧠 알고리즘

• 그리디(Greedy) + 정렬(Sorting) + Counter(해시맵) 기반 탐색

 

✔️ 동작 방식

• 크레인 무게 제한을 내림차순 정렬
• 가장 큰 크레인부터 처리
• 가장 큰 크레인도 옮길 수 없는 박스가 있으면 즉시 -1 반환
• 모든 박스를 옮기는 데 걸린 라운드 수(answer) 반환

---

 

 

🧾 코드

import sys
from collections import Counter

def _cr_max(b_s, crain_size):
    answer = 0
    for box_size in b_s.keys():
        if crain_size >= box_size:
            answer = max(answer, box_size)
    
    return answer
    

def _main(c_c, c_s, b_c, b_s):
    answer = 0
    c_s.sort(reverse=True)

    while b_s:
        answer += 1
        for now_c_idx in range(len(c_s)):
            if b_s:
                now_max_size = _cr_max(b_s, c_s[now_c_idx])
                if now_max_size:
                    b_s[now_max_size] -= 1
                    if b_s[now_max_size] == 0:
                        b_s.pop(now_max_size)
                else:
                    if now_c_idx == 0: # 젤 큰 크레인도 못담으면
                        return -1
                    else:
                        break
    return answer
            

c_count = int(sys.stdin.readline().rstrip())
c_size = list(map(int, sys.stdin.readline().rstrip().split()))
b_count = int(sys.stdin.readline().rstrip())
b_size = Counter(list(map(int, sys.stdin.readline().rstrip().split())))

print(_main(c_count, c_size, b_count, b_size))

---

 

 

⏱️ 시간 복잡도

while b_s : 조건 만족시 까지 탐색 ( 선형 시간 복잡도 )
	for now_c_idx in range(len(c_s)) : 큰 크레인 부터 탐색 ( 선형 시간 복잡도 )
		now_max_size = _cr_max(b_s, c_s[now_c_idx]) : 최대 박스 탐색 ( 선형 시간 복잡도 )
        
해당 알고리즘 시간 복잡도 : 삼차형 시간 복잡도 ( O(n ** 3) )