0과 1로만 이루어진 정수 배열 nums가 있다고 가정해 보겠습니다. 우리가 사용할 수 있는 연산은 다음과 같습니다. 배열에서 인덱스 i를 하나 선택하면, 해당 위치의 요소와 그 오른쪽에 있는 모든 숫자를 한 번에 뒤집습니다(0은 1로, 1은 0으로). 이때 배열의 모든 원소를 0으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 문제입니다.
문제 예시
입력이 [1, 0, 1]이라면 출력은 3이 됩니다.
- 인덱스 0에서 연산 수행 →
[0, 1, 0] - 인덱스 1에서 연산 수행 →
[0, 0, 1] - 인덱스 2에서 연산 수행 →
[0, 0, 0]
총 세 번의 연산으로 모든 원소가 0이 되었으므로 정답은 3입니다.
접근 방법
이 문제는 왼쪽부터 차례대로 살펴보면서, 각 위치에서 현재 값이 1이라면 그 시점에 반드시 한 번의 연산을 수행해야 한다는 아이디어로 해결할 수 있습니다. 핵심은 각 인덱스까지 누적된 연산 횟수를 추적하여, 현재 위치의 실제 상태(원래 값 + 누적된 뒤집기 횟수)를 파악하는 것입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- n을 배열 nums의 크기로 설정합니다.
- 크기가 n인 배열 op를 선언합니다. op[i]는 인덱스 i까지 수행된 연산(뒤집기) 횟수의 누적합을 의미합니다.
- 정답을 저장할 변수 ret을 0으로 초기화합니다.
- i를 0부터 배열 끝까지 반복하면서 다음을 수행합니다.
- i - 1 >= 0이면, op[i]에 op[i - 1]을 더해 누적 연산 횟수를 갱신합니다.
- (nums[i] + op[i])가 홀수라면, 즉 현재 위치의 유효 값이 1이라면 op[i]를 1 증가시키고 ret도 1 증가시킵니다. 이는 해당 위치에서 새로운 연산을 수행했다는 의미입니다.
연산은 선택한 인덱스부터 오른쪽 끝까지 모두 뒤집기 때문에, 각 위치의 최종 상태는 '원래 값 + 지금까지의 연산 횟수'를 2로 나눈 나머지(패리티)로 결정됩니다. 따라서 비트 AND 연산(& 1)으로 홀짝 여부를 빠르게 확인할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& nums) {
int n = nums.size();
vector<int> op(n);
int ret = 0;
for (int i = 0; i < nums.size(); i++) {
if (i - 1 >= 0) {
op[i] += op[i - 1];
}
if ((nums[i] + op[i]) & 1) {
op[i]++;
ret++;
}
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = {1,0,1};
cout << (ob.solve(v));
}입력
{1,0,1}출력
3
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 누적 연산 횟수를 저장하기 위한 크기 n의 배열 하나만 사용하므로 공간 복잡도 역시 O(n)입니다. 매우 효율적인 해결 방법입니다.