[백준 / 1092] 배

in Problem Solving on BaekJoon


날짜: 2021년 7월 21일
소요 시간: 42분 53초
카테고리: 그리디 알고리즘, 정렬
태그: gold.5, 1092, 파이썬

백준 1092 - 배

입출력 예시

예제 입력예제 출력
3 
6 8 9 
5 
2 5 2 4 71

내가 적은 코드

import sys

N = int(sys.stdin.readline())
crane = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
M = int(sys.stdin.readline())
box = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)

count = 0
if max(crane) < max(box):
    print(-1)
else:
    while len(box) != 0:
        for i in crane:
            if len(box) == 0:
                break
            else:
                for j in range(len(box)):
                    if i >= box[j]:
                        box.pop(j)
                        break
        count += 1
    print(count)

풀이 과정

정렬된 crane과 box 리스트의 0번째 인자를 비교하여 box의 0번째 인자가 더 크다면 (상자를 옮길 수 있는 크레인이 없는 경우) -1을 출력한다.

box의 인자가 한개도 없어질 때까지 crane 리스트의 가용 무게에 맞는 상자를 box 리스트와 비교한다.
만약 상자의 무게가 가용 무게를 넘어서게 된다면 그 다음 상자와 무게를 비교한다.

크레인으로 상자를 옮길 때 마다 box 리스트에서 그 상자를 삭제한다.

crane 리스트를 한바퀴 반복했을 경우 count를 1씩 더해준다.

만약 box 리스트에 인자가 하나도 없을 경우, 반복을 멈추고

Python3으로 실행 시 시간초과가 나서 PyPy3로 실행해서 성공하였다.
Python3과 PyPy3의 실행 속도 차이의 이유는 여기를 참조

베스트 코드

import sys

n = int(sys.stdin.readline())
crane = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
m = int(sys.stdin.readline())
box = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)

def test(t):
	if n*t < m:
		return False
	for i in range(t, m, t):
		if box[i] > crane[i//t]:
			return False
	return True
def bs(fun, l, r):
	while l <= r:
		mid = (l+r)//2
		if fun(mid):
			ans = mid
			r = mid-1
		else:
			l = mid+1
	return ans

if crane[0] < box[0]:
	print(-1)
else:
    print(bs(test, 1, m))

반성

  • 베스트 코드로 풀었을 때 Python3으로 실행했음에도 PyPy3로 실행한 내 코드보다 무려 50배가 더 빨랐다…
  • 분할 정복으로 풀어버리니까 시간적인 차이가 이렇게 난다는 걸 체감할 수 있는 좋은 예시였다.
  • 이론적으로 자료구조를 공부하긴 했지만 이렇게 실제로 코드로 활용하려면 더 익숙해 질 필요가 있는 것 같다.


© 2021. by hminkim