정수를 포함하는 두 개의 배열이 있다고 가정합니다. 한 목록에는 일부 단위 너비 상자의 높이가 포함되고 다른 배열에는 godown의 방 높이가 포함됩니다. 방의 번호는 0...n이고 방의 높이는 배열 godown의 해당 인덱스에 제공됩니다. 우리는 godown에 밀어 넣을 수 있는 상자의 수를 찾아야 합니다. 몇 가지를 염두에 두어야 합니다.
-
상자를 서로 겹칠 수 없습니다.
-
상자의 순서는 변경될 수 있습니다.
-
상자는 왼쪽에서 오른쪽으로만 godown에 놓입니다.
상자가 방의 높이보다 높으면 오른쪽에 있는 모든 상자와 함께 상자를 아래쪽으로 밀어 넣을 수 없습니다.
따라서 입력이 상자 =[4,5,6], godown =[4, 5, 6, 7]과 같으면 출력은 1이 됩니다. 상자는 하나만 삽입할 수 있습니다. 첫 번째 방의 크기는 4이고 나머지 상자는 첫 번째 방을 통해 밀어 넣어야 하고 길이가 다른 상자보다 작기 때문에 나머지는 godown으로 밀어 넣을 수 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
목록 상자 정렬
-
curmin :=godown의 첫 번째 요소를 포함하는 새 목록
-
cm :=커민[0]
-
범위 1에서 godown 크기까지의 i에 대해
-
cur :=godown[i]
-
cur
-
cm :=커
-
-
curmin 끝에 cm 삽입
-
-
나는 :=0
-
j :=godown의 크기 -1
-
r :=0
-
동안 j>=0 및 i <상자 크기, 수행
-
curmin[j]>=box[i]이면
-
나는 :=나는 + 1
-
r :=r + 1
-
-
j :=j - 1
-
-
리턴 r
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(boxes, godown): boxes.sort() curmin = [godown[0]] cm = curmin[0] for i in range(1, len(godown)): cur = godown[i] if cur < cm: cm = cur curmin.append(cm) i,j = 0, len(godown)-1 r = 0 while j >= 0 and i < len(boxes): if curmin[j] >= boxes[i]: i += 1 r += 1 j -= 1 return r print(solve([4,5,6], [4, 5, 6, 7]))
입력
[4,5,6], [4, 5, 6, 7]
출력
1