정수를 포함하는 두 개의 배열이 있다고 가정합니다. 한 목록에는 일부 단위 너비 상자의 높이가 포함되고 다른 배열에는 godown의 방 높이가 포함됩니다. 방의 번호는 0...n이고 방의 높이는 배열 godown의 해당 인덱스에 제공됩니다. 우리는 godown에 밀어 넣을 수 있는 상자의 수를 찾아야 합니다. 몇 가지를 염두에 두어야 합니다.
-
상자를 서로 겹칠 수 없습니다.
-
상자의 순서는 변경될 수 있습니다.
상자는 어느 쪽에서나 godown에 넣습니다. 왼쪽 또는 오른쪽이 될 수 있습니다. 상자가 방의 높이보다 높으면 오른쪽에 있는 모든 상자와 함께 상자를 아래쪽으로 밀어 넣을 수 없습니다.
따라서 입력이 상자 =[4, 5, 6], godown =[4, 5, 6, 7]과 같으면 출력은 3이 됩니다. 입력으로 제공된 세 개의 상자는 모두 godown에 넣을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
목록 상자를 내림차순으로 정렬
-
내가 :=0
-
r :=godown의 크기 - 1
-
바이 :=0
-
렛 :=0
-
동안 bi <상자 크기 및 l <=r, do
-
godown[l]> godown[r]이면
-
상자[bi] <=godown[l]이면
-
렛 :=렛 + 1
-
l :=l + 1
-
-
그렇지 않으면
-
상자[bi] <=godown[r]이면
-
렛 :=렛 + 1
-
r :=r - 1
-
-
-
바이 :=바이 + 1
-
-
-
리턴 렛
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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