[백준] 1092번 배 _ Python

[초기 접근 방법]

1) 구현

박스와 크레인을 내림차순 정렬을 한다.

무거운 박스부터 무거운 크레인을 배정한다.

배정을 못할 시, 크레인 순환을 +1 한다.

 

→ 무거운 박스는 옮기지 못하지만 작은 박스는 옮길 수 있음

 

 

2) 이분 탐색

현재 박스 무게에 맞는 크레인을 이분 탐색으로 배정한다.

이 때 박스 무게 초과인 upper_bound가 아닌 이상인 lower_bound로 탐색을 해야 한다.

모든 박스를 효율적으로 이동하기 위해, 무거운 박스부터 크레인으로 옮긴다.

 

 → ?

 

 

[생각]

이분 탐색으로 풀리지 않자 검색하여 코드를 참고했다.

 

그리디로 푸는 것..😂

그리디 문제인지 알고 접근하면, 바로 그리디적으로 생각하게 되는데

유형을 모르고 푸니 완전탐색, 백트래킹, 이분탐색, dp 여러 측면에서 생각하게 되는 것 같다..

코테에서는 문제 유형을 모르니 이런 부분에 대해서 다양하고 빠르게 사고하는 연습이 필요함을 느꼈던 문제였다.

 

 

[코드]

- 틀린 코드(이분 탐색)

# 박스는 내림차순 (그리디)

# 풀이 시간 : 1시간(일반 구현) + 55분(이분탐색)
# 시간복잡도 : O(MlogN) → 박스 수 * log(크레인 수)
# 공간복잡도 : O(N 또는 M)
# 참고 : -


# lower_bound로 박스 무게에 맞는 크레인 찾기
def bns(boxWeight, start, end):

    while start < end:
        mid = (start + end) // 2

        if boxWeight > crane[mid]: # 박스 무게가 클 시
            start = mid + 1

        else: # 크레인 무게가 클 시
            end = mid

    # 끝까지 탐색했으나 박스에 맞는 크레인이 없을 시, 다음 순환
    if not crane or boxWeight > crane[end]:
        return -1
    else:
        return end

N = int(input())
crane = list(map(int, input().split()))

M = int(input())
box = list(map(int, input().split()))

crane.sort()
box.sort(reverse=True)

boxes = []
for b in box:
    boxes.append(b)

if box[-1] > crane[-1]:
    print(-1)

else:
    useCrane = []
    circular = 0

    # 박스를 모두 옮기면 끝
    while boxes:
        circular += 1 # 크레인 순환 체크

        for b in box:
            idx = bns(b, 0, len(crane)-1)

            # 현재 박스에 맞는 크레인이 없을 때
            if idx == -1:
                continue

            # 현재 순환에서 크레인 사용
            use = crane[idx]
            useCrane.append(use)
            crane.remove(use)
            boxes.remove(b)

        # 현재 옮겨야 할 박스 초기화
        box.clear()
        for k in boxes:
            box.append(k)

        # 크레인 복원
        for u in useCrane:
            crane.append(u)
        crane.sort()

        # 사용한 크레인 초기화
        useCrane.clear()


    print(circular)

 

 

- 정답 코드(그리디)

# 풀이 시간 : 1시간(일반구현) + 55분(이분탐색) + 10분(그리디)
# 시간복잡도 : O(MN*M)
# 공간복잡도 : O(N 또는 M)
# 참고 : https://codinghejow.tistory.com/249

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)

time = 0
if crane[0] < box[0]:
    print(-1)

else:
    while box:
        for c in crane:
            for b in box:
                if c >= b:
                    box.remove(b)
                    break

        time += 1

    print(time)

 

 

 

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

1092번: 배