0과 1로만 구성된 이진 리스트 nums가 있다고 가정해 봅시다. 여기서 0은 빈 칸을, 1은 공이 놓여 있는 칸을 의미합니다. 우리의 목표는 nums와 같은 크기의 새로운 리스트 L을 만드는 것입니다. 이때 L[i]에는 모든 공을 i번째 위치로 이동시키는 데 필요한 총 거리가 저장됩니다. 인덱스 j에 있는 공을 인덱스 i로 옮길 때의 거리는 |j − i|로 정의됩니다.
문제 예시
예를 들어 nums = [1, 1, 0, 1]이 주어지면 결과는 [4, 3, 4, 5]가 됩니다.
- L[0] = |0 − 0| + |1 − 0| + |3 − 0| = 4
- L[1] = |0 − 1| + |1 − 1| + |3 − 1| = 3
- L[2] = |0 − 2| + |1 − 2| + |3 − 2| = 4
- L[3] = |0 − 3| + |1 − 3| + |3 − 3| = 5
즉, 모든 공을 L[1] 위치로 모으려면 인덱스 0의 공을 거리 1만큼, 인덱스 3의 공을 거리 2만큼 이동시켜야 합니다.
해결 전략
각 위치마다 모든 공과의 거리를 일일이 계산하면 O(n²)의 시간 복잡도가 발생합니다. 하지만 왼쪽과 오른쪽에 있는 공의 개수와 인덱스 합을 미리 추적하면 한 번의 순회만으로 답을 갱신할 수 있어 O(n) 시간 안에 효율적으로 해결할 수 있습니다.
다음 단계로 진행합니다.
- nums가 비어 있다면 빈 리스트를 반환합니다.
- left_count, right_count, left_sum, right_sum을 0으로 초기화하고 빈 result 리스트를 준비합니다.
- 첫 번째 순회에서 값이 1(공)인 경우 right_count를 증가시키고 해당 인덱스를 right_sum에 더합니다.
- 두 번째 순회에서는 아래 작업을 반복합니다.
- (left_sum + right_sum) 값을 result 끝에 추가합니다.
- 현재 위치에 공이 있다면 right_count를 1 감소시키고 left_count를 1 증가시킵니다.
- left_sum에 left_count를 더하고, right_sum에서 right_count를 뺍니다.
- 완성된 result를 반환합니다.
구현 예제
다음 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.
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]