문제 개요
이진(binary) 배열 nums와 값 k가 주어졌다고 가정해 봅시다. 한 번의 이동(move)에서는 인접한 두 인덱스를 선택해 그 값을 서로 교환(swap)할 수 있습니다. 이때 배열 nums에 k개의 연속된 1이 존재하도록 만들기 위해 필요한 최소 이동 횟수를 구하는 것이 목표입니다.
예를 들어 입력이 nums = [1,0,0,1,0,1,0,1], k = 3이라면 출력은 2가 됩니다. 첫 번째 스왑으로 배열을 [1,0,0,1,0,1,0,1]에서 [1,0,0,0,1,1,0,1]로 바꾸고, 두 번째 스왑으로 [1,0,0,0,1,1,1,0]으로 만들면 되기 때문입니다.
접근 방법
이 문제는 슬라이딩 윈도우(sliding window) 기법과 중앙값(median)의 성질을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열에서 1이 위치한 인덱스들을 순서대로
loc리스트에 저장합니다. k개의 1을 연속되게 모으려면 특정 기준 위치를 중심으로 모아야 하는데, 이때 기준 위치가 해당 구간의 중앙값일 때 총 스왑 비용이 최소화됩니다.- 윈도우에 포함된 1의 개수가
k를 초과하면 가장 왼쪽 원소를 제거하고(포인터j증가), 누적 비용val을 차감하며 상태를 유지합니다. - 윈도우 내 1의 개수가 정확히
k가 될 때마다 현재 비용val과 정답ans를 비교하여 최솟값을 갱신합니다.
이 방식은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.
알고리즘 단계
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
j := 0
val := 0
ans := 999999
loc := 새로운 리스트
nums의 각 인덱스 i와 값 x에 대해 다음을 수행합니다:
x가 0이 아니라면:
i를 loc의 끝에 삽입합니다.
m := (j + len(loc) - 1) // 2
val := val + loc[-1] - loc[m] - (len(loc) - j) // 2
만약 len(loc) - j > k라면:
m := (j + len(loc)) // 2
val := val - (loc[m] - loc[j] - (len(loc) - j) // 2)
j := j + 1
만약 len(loc) - j == k라면:
ans := min(ans, val)
ans를 반환합니다.
구현 예시
더 나은 이해를 위해 다음 파이썬 구현을 살펴보겠습니다.
def solve(nums, k):
j = val = 0
ans = 999999
loc = []
for i, x in enumerate(nums):
if x:
loc.append(i)
m = (j + len(loc) - 1)//2
val += loc[-1] - loc[m] - (len(loc)-j)//2
if len(loc) - j > k:
m = (j + len(loc))//2
val -= loc[m] - loc[j] - (len(loc)-j)//2
j += 1
if len(loc)-j == k:
ans = min(ans, val)
return ans
nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))입력
[1,0,0,1,0,1,0,1], 3
출력
2