문제 설명
0과 1로 이루어진 숫자 리스트 nums와 정수 값 k가 주어진다고 가정해 봅시다.
여기에는 길이가 k인 부분 리스트(연속된 구간)를 선택해 뒤집는 연산이 있습니다. 뒤집기를 수행하면 해당 구간 안의 모든 1은 0으로, 모든 0은 1로 바뀝니다. 우리는 리스트의 모든 1을 0으로 만들기 위해 필요한 최소 연산 횟수를 구해야 하며, 아무리 시도해도 모두 0으로 만들 수 없다면 -1을 반환해야 합니다.
예를 들어 입력이 nums = [1,1,1,0,0,1,1,1], k = 3이라면 출력은 2가 됩니다. 앞의 세 개 숫자를 한 번 뒤집고, 마지막 세 개 숫자를 한 번 더 뒤집으면 전체가 0이 되기 때문입니다.
풀이 방법
이 문제는 그리디(Greedy) 기법과 XOR 연산을 활용하면 효율적으로 해결할 수 있습니다. 리스트를 왼쪽부터 차례대로 탐색하면서, 현재 위치의 실질적인 값이 1이라면 반드시 그 위치에서 시작하는 뒤집기를 수행해야 합니다. 각 뒤집기의 영향이 끝나는 지점을 to_conv 배열에 미리 표시해 두고, XOR 연산을 통해 현재 위치가 이전 뒤집기의 영향을 받았는지 여부를 추적합니다.
단계별 접근 방식은 다음과 같습니다 −
n := nums의 크기
res := 0, flipped := 0으로 초기화
to_conv := 크기가 n인 리스트를 생성하고 0으로 채우기
i를 0부터 n-1까지 반복:
flipped := flipped XOR to_conv[i]
cur := nums[i]
cur := cur XOR flipped
만약 cur이 1과 같다면:
flipped := flipped XOR 1
res := res + 1
만약 i + k - 1 >= n이라면:
-1 반환
만약 i + k < n이라면:
to_conv[i + k] := 1
res 반환
예제 코드
더 나은 이해를 돕기 위해 다음 구현 예시를 살펴보겠습니다 −
class Solution:
def solve(self, nums, k):
n = len(nums)
res = 0
flipped = 0
to_conv = [0] * n
for i in range(n):
flipped ^= to_conv[i]
cur = nums[i]
cur ^= flipped
if cur == 1:
flipped ^= 1
res += 1
if i + k - 1 >= n:
return -1
if i + k < n:
to_conv[i + k] = 1
return res
ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))
입력
[1,1,1,0,0,1,1,1], 3
출력
2
복잡도 분석
이 알고리즘은 리스트를 단 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 뒤집기 영향 범위를 추적하기 위한 to_conv 배열이 추가로 필요하므로 공간 복잡도 역시 O(n)입니다.