상자라는 이진 문자열이 있다고 가정합니다. 여기서 상자[i]는 '0'은 i번째 상자가 비어 있음을 나타내고 '1'은 하나의 공이 포함되어 있음을 나타냅니다. 이제 한 번의 작업으로 상자에서 인접한 상자로 공 하나를 이동할 수 있습니다. 그렇게 하고 나면 어떤 상자에는 하나 이상의 공이 있을 수 있습니다. 크기가 n인 배열 답을 찾아야 합니다. 여기서 answer[i]는 모든 공을 i번째 상자로 이동하는 데 필요한 최소 작업 수입니다.
따라서 입력이 상자 ="1101"과 같으면 출력은 [4, 3, 4, 5]
가 됩니다.-
첫 번째 상자에 모든 공을 넣으려면 상자 2에서 한 번의 작업으로, 마지막 볼에서 세 번의 작업으로 총 4번의 작업을 가져와야 합니다.
-
모든 공을 두 번째 상자에 넣으려면 상자 1에서 한 번의 작업으로, 마지막 볼에서 두 번의 작업으로 가져와서 총 3번의 작업을 수행해야 합니다.
-
세 번째 상자에 모든 공을 넣으려면 상자 2에서 각각 한 번의 작업으로 마지막 작업을 가져와야 하고 상자 1에서 두 번의 작업으로 총 4개의 작업을 가져와야 합니다.
-
마지막 상자에 모든 공을 넣으려면 상자 1에서 3번의 작업을, box 2에서 2번의 작업을 가져와서 총 5번의 작업을 수행해야 합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
왼쪽 :=0, 오른쪽 :=0, 거리 :=0
-
범위 0에서 상자 크기 - 1에 있는 i의 경우 수행
-
box[i]가 "1"과 같으면
-
dist :=dist + i
-
i가 0과 같으면
-
왼쪽 :=왼쪽 + 1
-
-
그렇지 않으면
-
오른쪽 :=오른쪽 + 1
-
-
-
-
arr :=목록이고 처음에 dist를 그 안에 넣습니다.
-
범위 1에서 상자 크기 - 1에 있는 i의 경우 수행
-
삽입 arr[i-1] + 왼쪽 - 오른쪽 끝에 arr
-
box[i]가 "1"과 같으면
-
왼쪽 :=왼쪽 + 1
-
오른쪽 :=오른쪽 - 1
-
-
-
반환 arr
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(boxes):
left = 0
right = 0
dist = 0
for i in range(len(boxes)):
if boxes[i] == "1":
dist += i
if i == 0:
left += 1
else:
right += 1
arr = [dist]
for i in range(1, len(boxes)):
arr.append(arr[i-1] + left - right)
if boxes[i] == "1":
left += 1
right -= 1
return arr
boxes = "1101"
print(solve(boxes)) 입력
"1101"
출력
[4, 3, 4, 5]