Python으로 창고에 넣을 수 있는 상자 개수를 구하는 프로그램

문제 설명

정수로 이루어진 두 개의 배열이 있다고 가정해 보겠습니다. 하나는 단위 폭을 가진 상자들의 높이를 담고 있고, 다른 하나는 창고(godown) 안에 있는 방들의 높이를 담고 있습니다. 방은 0부터 n까지 번호가 매겨져 있으며, 각 방의 높이는 godown 배열의 해당 인덱스에 저장되어 있습니다. 우리가 구해야 하는 값은 창고에 밀어 넣을 수 있는 상자의 개수입니다.

이때 다음 조건들을 유의해야 합니다.

• 상자를 서로 위에 쌓을 수는 없습니다.
• 상자를 넣는 순서는 자유롭게 바꿀 수 있습니다.

상자는 왼쪽이나 오른쪽 어느 쪽에서든 창고에 넣을 수 있습니다. 만약 어떤 상자가 들어가려는 방보다 높이가 크다면, 그 상자뿐만 아니라 그 오른쪽에 있는 모든 상자들도 더 이상 창고에 넣을 수 없습니다.

예를 들어 입력이 boxes = [4, 5, 6], godown = [4, 5, 6, 7]이라면 출력은 3이 됩니다. 입력으로 주어진 세 개의 상자 모두 창고에 넣을 수 있기 때문입니다.

해결 접근 방법

이 문제는 그리디(greedy) 기법과 투 포인터(two pointer) 기법을 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 상자 목록을 내림차순으로 정렬하여 큰 상자부터 배치를 시도합니다.
• 왼쪽 포인터 l은 0, 오른쪽 포인터 r은 godown의 마지막 인덱스로 초기화합니다.
• 매 단계마다 현재 접근 가능한 양쪽 끝 방 중 더 높은 쪽을 선택하고, 현재 상자가 그 방에 들어갈 수 있으면 상자를 넣은 뒤 해당 포인터를 안쪽으로 한 칸 이동시킵니다.
• 현재 상자가 들어갈 수 없다면 그 상자는 건너뛰고 다음 상자로 넘어갑니다.
• 모든 상자를 확인하거나 두 포인터가 교차할 때까지 반복한 후, 지금까지 넣은 상자의 개수를 반환합니다.

예제 코드 (Python)

아래 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(boxes, godown):
    boxes.sort(reverse=True)

    l, r = 0, len(godown) - 1
    bi, ret = 0, 0
    while bi < len(boxes) and l <= r:
        if godown[l] > godown[r]:
            if boxes[bi] <= godown[l]:
                ret += 1
                l += 1
        else:
            if boxes[bi] <= godown[r]:
                ret += 1
                r -= 1
        bi += 1

    return ret

print(solve([4, 5, 6], [4, 5, 6, 7]))

입력

[4, 5, 6], [4, 5, 6, 7]

출력

3