[BOJ] 1092 배

1092 배

그리디

1. 정렬
2. 정렬된 데이터를 처리하기

fail log

import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
cranes=sorted(map(int,input().split()),reverse=True)
M=int(input())
boxes=deque(sorted(map(int,input().split()),reverse=True))
cnt=0
while boxes:
    cnt+=1
    for crane in cranes:
        fail=0
        while boxes:
            if fail==len(boxes): break
            if boxes[0]<=crane: 
                boxes.popleft()
                break
            else:
                fail+=1
                boxes.append(boxes.popleft())
        boxes=deque(sorted(list(boxes),reverse=True))
print(cnt)

1. 그리디 문제다.
2. 35분만에 풀라고 했는데 1시간 9분동안에도 못 풀었다.
3. 저만큼 시간이 걸렸는데도 코드가 깔끔하지 못한 거 같다..
4. 풀지도 못하고 코드도 바보 같다...

import sys
from collections import deque
input=sys.stdin.readline
N=int(input())
cranes=list(map(int,input().split()))
M=int(input())
boxes=list(map(int,input().split()))

if max(cranes)<max(boxes):
    print(-1)
    sys.exit()
    
positions =[0]*N # 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
checked=[False]*M
cranes.sort(reverse=True)
boxes.sort(reverse=True)

result=0 # 몇분 옮겼나
count=0 # 박스를 몇번 옮겼나

while True:
    if count==len(boxes): break # 박스를 다 옮겼다면 종료
    for i in range(N): # 모든 크레인에 대해 각각 처리
        # 각 크레인 별로 posit에 기록해서 한바퀴(박스의 개수만큼) 다 돌면 끝, 그 다음 크레인으로 넘어감
        while positions[i]<len(boxes):
            # 아직 안 옮긴 박스 중에서 옮길 수 있는 박스를 만날 때까지 반복
            if not checked[positions[i]] and cranes[i]>=boxes[positions[i]]:
                checked[positions[i]]=True
                positions[i]+=1
                count+=1
                break
            positions[i]+=1
    result+=1
print(result)

1. 무거운 것부터 담으라고 한다. 그래야 최적의 솔루션을 보장할 수 있다.
2. O(NM)으로 풀어야 함
3. 한번 본 박스는 다시 보지 않도록 보장해야함.
4. 매 분마다, 모든 크레인에 대해 옮길 수 있는 박스를 옮기도록 한다.
5. 각 크레인 별로 처리하기
6. position으로 각 crane이 어디까지 체크했나 확인 ➡️ 만날 수 있는 것들은 다 처리 (이미 내림차순으로 정리돼있기에 가능)
7. check으로 옮겨진 박스 구분

#pypy로 돌려야 시간초과없이 통과
import sys

read = sys.stdin.readline

N = int(read())
cranes = list(map(int, read().split()))

M = int(read())
boxs = list(map(int, read().split()))

cranes.sort(reverse=True)
boxs.sort(reverse=True)

if boxs[0] > cranes[0]:
    print(-1)
    sys.exit()
else:
    time = 0

    while boxs:
        if not boxs:
            break

        for crane in cranes:
            for box in boxs:
                if crane >= box:
                    boxs.remove(box)
                    break

        time += 1

    print(time)

내가 틀린 이유
1. 작은 거부터 옮기도록 짰다.
2. 한바퀴 돌았다는 걸 어렵게 증명했다. 또 다른 for문이어도 됐을텐데 굳이 굳이 while로 하였음.

참고