[백준] 1092번 파이썬 _ 배

https://www.acmicpc.net/problem/1092

1092번: 배

 

문제유형 : 그리디, 정렬, 이분탐색 

 

문제풀이 : 

• 일반적인 그리디로 그냥 풀엇을때보다 이분탐색으로 풀면 10배정도 시간이 줄어든다.
• bisect 라이브러리를 이용하여 해당 크레인이 버틸수있는 무게의 가장 큰값을 찾을 수 있도록 했다.

 

삽질..

분명 맞는거같은데 시간초과가나서 헤맸는데 알고보니까 맨처음 예외처리를 안해줘서 그랬다. ㅜㅜ... 하ㅏㅏㅏㅏㅏㅏㅏ 

최대무게를 버틸수있는 크레인도 가장무거운 박스를 버티지 못하는경우를 따로 처리해줬어야했는데 풀다보니그냥 까먹어버렸다.

제발 극단적인 예외같은 경우 항상 문제풀기전에 수도코드라도 적어놓고 시작하자..

 

정답코드 : 

import sys
from bisect import *

input = sys.stdin.readline

n = int(input())
crain = list(map(int, input().split()))
k = int(input())
boxes = list(map(int, input().split()))

crain.sort(reverse=True)

boxes.sort()

if crain[0] < boxes[-1]:
    print(-1)
    exit()
    
cnt = 0
while boxes:
    #print("new round")
    cnt += 1
    for c in crain:
        right = bisect_right(boxes, c)
        #print(right)
        if boxes and boxes[right-1] <= c:
            boxes.pop(right-1)
            #print(boxes)

print(cnt)