1092 - 배

info

• 문제 보기: 1092 - 배
• 소요 시간: 💥1시간 초과
• 풀이 언어: python
• 체감 난이도: 4️⃣
• 리뷰 횟수: ✅✅

풀이 키워드

스포주의

그리디

I HATE GREEDY

풀이 코드

info

• 메모리: 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........🙄

tip

4608ms → 44ms 최적화하기

핵심은 crane[cdx] < box[-1]를 체크해서, 현재 가장 하중이 큰 크레인이 가장 가벼운 박스도 못 들어주면 바로 컷하고 1분을 기다리는 것이다. 발품 팔아본 결과 65% 지점의 테스트케이스가 이에 대해 평가하기 때문에, 해당 조건이 없으면 엄청나게 수행시간이 크게 찍힌다.

또한 bdx > remain-1 <-- 여기서 remain을 len(box)로 대체할 시 TLE를 받기에, 배제해야 한다. 파이썬 len()은 $O(1)$이지만 백준에서 간혹 len() 하나 차이로 TLE를 받는 경우가 있다.

4608ms

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)

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
    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문에선 다음과 같이 작동할 것이다.

1. 7짜리 crane이 첫번째 6 box를 들고 해당 box를 remove --> (box: 6 3 3)
2. 4짜리 crane이 6 box를 들 수 있는지 판단한 후, 안되므로 다음 3 box 확인 후 들고 해당 box를 remove --> (box: 6 3)
3. 4짜리 crane이 6 box를 들 수 있는지 판단한 후, ... (생략)

여기서, 마지막에 4짜리 crane이 6 box를 들 수 있는지 없는지 판단할 필요가 있었을까? 를 생각해보면, 충분히 최적화 가능한 로직임을 알 수 있다.

내림차순 정렬되어 있으므로, 앞 crane이 불가능하다고 판단한 box는 다음 crane도 당연히 불가능하기 때문이다.

따라서, 이전 crane이 마지막으로 탐색한 box의 인덱스는 전체 crane을 한 번 순회하는 내내 살려둘 필요가 있다.

메모

• while 내부의 for문 순회를 박스 기준으로 할 지 아니면 크레인 기준으로 할 지 약간 헷갈렸다. 따라서 while로만 반복하면서 box와 crane의 인덱스를 각각 조정해주는 방식으로 작성했다.

  • 그렇다. 가독성 때문이었다. 근데 성능적으로도 이득을 봤네?

• [소스 보기] <-- 요건 어떻게 40ms??