[Python] 백준 1092. 배 풀이 - 파이썬 탐욕 알고리즘(그리디) 구현 (5)

백준 1092. 배

🏀 문제 아이디어 정리

⚡ 시간초과를 위해 position배열을 활용하면, 무거워서 박스를 못옮겼을 때, position을 +1해줘서 다음에는 그 박스 다음 박스부터 시행하게 한다. 때문에 박스와 크레인을 내림차순으로 정렬해줘야 한다.

🎾 풀이 코드

n = int(input())
crane = list(map(int, input().split()))
m = int(input())
box = list(map(int, input().split()))

# ⚡ 내림차순 정렬
crane.sort(reverse = True)
box.sort(reverse = True)

time = 0 # 시간
checked = [0 for _ in range(m)] # 박스를 옮겼는지 여부
count = 0 # 옮긴 박스의 개수 

positions = [0] * n

if max(box) > max(crane):
    print(-1)
else:
    while count < len(box):
        for i in range(n): # 크레인에 대하여
            while positions[i] < len(box):
            # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
                if not checked[positions[i]] and crane[i] >= box[positions[i]]:
                    checked[positions[i]] = True
                    positions[i] += 1
                    count += 1
                    break
                positions[i] += 1
        time += 1
    print(time)