1092 - 배
- 문제 보기: 1092 - 배
- 소요 시간: 💥1시간 초과
- 풀이 언어:
python - 체감 난이도: 4️⃣
- 리뷰 횟수: ✅✅
풀이 키워드
스포주의
그리디
풀이 코드
- 메모리: 32140 KB
- 시간: 44 ms
import sys
input = sys.stdin.readline
# 크레인과 박스를 내림차순 정렬하고
# batch(=크레인 개수) 단위로 큰 박스부터 처리
def solution():
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)
# corner case
if crane[0] < box[0]:
print(-1)
return
ans = 0
bdx, cdx = 0, 0
remain = m
while box:
# check crane availability
if box[bdx] <= crane[cdx]:
box.remove(box[bdx])
remain -= 1
cdx += 1
else:
bdx += 1
# bound check
# 위치 중요: while 앞단에 두면 ans += 1 하나 빠짐
## 크레인 다 쓰는중 --> 1분 ㄱㄷ
## 박스 한번 훑음 --> 들어줄 크레인 없음 --> 1분 ㄱㄷ
## 가장 하중 큰 크레인이 가장 가벼운 박스도 못들어줌 --> 1분 ㄱㄷ
if bdx > remain-1 or cdx > n-1 or crane[cdx] < box[-1]:
bdx, cdx = 0, 0
ans += 1
print(ans)
if __name__ == '__main__':
solution()
풀이 해설
WA 코드
import sys
from collections import deque
input = sys.stdin.readline
def solution():
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)
# corner case
if crane[0] < box[0]:
print(-1)
return
q = deque(box) # remained boxes
ans = 0
while q:
#print(q)
sz = len(q)
last_cdx = 0
for _ in range(sz):
if last_cdx > n-1:
break
b = q.popleft()
if b <= crane[last_cdx]:
last_cdx += 1
else:
q.append(b)
ans += 1
print(ans)
if __name__ == '__main__':
solution()
55분 쯤에 WA를 받아서 반례를 찾아보니 다음의 case가 있었다.
# 입력
4
1 2 3 4
8
1 1 2 2 3 3 4 4
# 정답
2
이게 3이 나와서 디버깅하니
당장 못옮기는 박스를 큐에 다시 넣으면서 큐 정렬이 깨지는 것이 원인이었다.
--> 그래서 heapq로 매 순회마다 내림차순 유지시키려고 했는데 TLE가 떴다.
--> 그래서2 done으로 플래그 틀어막고 무한 순회하는 방식으로 수정했다.
--> 통과했는데....음.........4608ms........🙄
4608ms → 44ms 최적화하기
핵심은 crane[cdx] < box[-1]를 체크해서, 현재 가장 하중이 큰 크레인이 가장 가벼운 박스도 못 들어주면 바로 컷하고 1분을 기다리는 것이다. 발품 팔아본 결과 65% 지점의 테스트케이스가 이에 대해 평가하기 때문에, 해당 조건이 없으면 엄청나게 수행시간이 크게 찍힌다.
또한 bdx > remain-1 <-- 여기서 remain을 len(box)로 대체할 시 TLE를 받기에, 배제해야 한다. 파이썬 len()은 이지만 백준에서 간혹 len() 하나 차이로 TLE를 받는 경우가 있다.
- 4608ms
- 44ms
def solution():
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)
# corner case
if crane[0] < box[0]:
print(-1)
return
ans = 0
remained = m
done = [False] * m
while remained > 0:
last_cdx = 0
for bdx in range(m):
if last_cdx > n-1:
break
if not done[bdx]:
# check crane availability
if box[bdx] <= crane[last_cdx]:
done[bdx] = True
last_cdx += 1
remained -= 1
ans += 1
print(ans)
def solution():
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)
# corner case
if crane[0] < box[0]:
print(-1)
return
ans = 0
bdx, cdx = 0, 0
remain = m
while box:
# check crane availability
if box[bdx] <= crane[cdx]:
box.remove(box[bdx])
remain -= 1
cdx += 1
else:
bdx += 1
if bdx > remain-1 or cdx > n-1 or crane[cdx] < box[-1]:
bdx, cdx = 0, 0
ans += 1
print(ans)
2중 for문 안 쓴 이유
이 문제는 2중 for문으로 작성한 AC들이 많은데, 굳이 따라하진 않았다.
2중 for문으로 로직을 구성하면 다음의 케이스에서 약간 비효율적으로 작동하기 때문이다.
# 입력
crane: 7 4 4
box : 6 6 3 3
2중 for문에선 다음과 같이 작동할 것이다.
- 7짜리 crane이 첫번째 6 box를 들고 해당 box를 remove --> (box: 6 3 3)
- 4짜리 crane이 6 box를 들 수 있는지 판단한 후, 안되므로 다음 3 box 확인 후 들고 해당 box를 remove --> (box: 6 3)
- 4짜리 crane이 6 box를 들 수 있는지 판단한 후, ... (생략)
여기서, 마지막에 4짜리 crane이 6 box를 들 수 있는지 없는지 판단할 필요가 있었을까? 를 생각해보면, 충분히 최적화 가능한 로직임을 알 수 있다.
내림차순 정렬되어 있으므로, 앞 crane이 불가능하다고 판단한 box는 다음 crane도 당연히 불가능하기 때문이다.
따라서, 이전 crane이 마지막으로 탐색한 box의 인덱스는 전체 crane을 한 번 순회하는 내내 살려둘 필요가 있다.
메모
-
while내부의for문 순회를 박스 기준으로 할 지 아니면 크레인 기준으로 할 지 약간 헷갈렸다. 따라서while로만 반복하면서box와crane의 인덱스를 각각 조정해주는 방식으로 작성했다.- 그렇다. 가 독성 때문이었다. 근데 성능적으로도 이득을 봤네?
-
[소스 보기] <-- 요건 어떻게 40ms??