0과 1만 포함하는 nums라는 이진 목록이 있다고 가정합니다. 여기서 0은 빈 셀을 나타내고 1은 셀이 공으로 채워져 있음을 나타냅니다. L[i]는 모든 공을 L[i]로 이동하는 데 필요한 총 거리로 설정되어 있으며 크기도 nums 크기와 동일한 L을 말하는 새 목록을 찾아야 합니다. 여기서 인덱스 j에서 인덱스 i까지 공을 이동하는 거리는 |j - i|입니다.
따라서 입력이 nums =[1, 1, 0, 1]과 같으면 출력은 [4, 3, 4, 5]가 됩니다. 왜냐하면
- L[0] =|0 - 0| + |1 - 0| + |3 - 0|
- L[1] =|0 - 1| + |1 - 1| + |3 - 1|
- L[2] =|0 - 2| + |1 - 2| + |3 - 2|
- L[3] =|0 - 3| + |1 - 3| + |3 - 3|
따라서 모든 공을 L[1]로 이동하려면 공을 인덱스 0에서 거리 1로 이동하고 인덱스 3에서 거리 2로 공을 이동해야 합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- nums가 비어 있으면
- 새 목록 반환
- left_count :=0
- right_count :=0
- left_sum :=0
- right_sum :=0
- 결과:=새 목록
- 숫자 단위의 각 인덱스와 값에 대해 다음을 수행합니다.
- num이 0이 아니면
- right_count :=right_count + 1
- right_sum :=right_sum + 인덱스
- num이 0이 아니면
- 숫자 단위의 각 인덱스와 값에 대해 다음을 수행합니다.
- 결과 끝에 (left_sum + right_sum) 삽입
- num이 0이 아니면
- right_count :=right_count - 1
- left_count :=left_count + 1
- left_sum :=left_sum + left_count
- right_sum :=right_sum - right_count
- 반환 결과
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums): if not nums: return [] left_count = right_count = 0 left_sum = right_sum = 0 result = [] for index, num in enumerate(nums): if num: right_count += 1 right_sum += index for index, num in enumerate(nums): result.append(left_sum + right_sum) if num: right_count -= 1 left_count += 1 left_sum += left_count right_sum -= right_count return result nums = [1, 1, 0, 1] print(solve(nums))
입력
[1, 1, 0, 1]
출력
[4, 3, 4, 5]