문제 설명
'0'과 '1'로만 이루어진 문자열이 주어졌다고 가정해 보겠습니다. 이러한 문자열은 일정 개수의 '0'(0개일 수도 있음) 뒤에 일정 개수의 '1'(역시 0개일 수도 있음)이 이어지는 형태일 때 단조 증가(monotonic increasing)라고 합니다.
우리는 '0'과 '1'로 구성된 문자열 S를 가지고 있으며, 임의의 '0'을 '1'로 바꾸거나 '1'을 '0'으로 뒤집을(flip) 수 있습니다. 이때 S를 단조 증가 문자열로 만들기 위해 필요한 최소 뒤집기 횟수를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 "010110"이라면 출력은 2입니다. 두 번 뒤집으면 "011111" 또는 "000111"을 만들 수 있기 때문입니다.
풀이 접근 방법
이 문제는 문자열을 왼쪽에서 오른쪽으로 한 번만 훑으며 해결할 수 있는 그리디(Greedy) 방식으로 접근합니다. 핵심 아이디어는 다음과 같습니다.
- n := S의 길이로 설정하고, flipCount := 0, oneCount := 0으로 초기화합니다.
- i를 0부터 n-1까지 반복합니다.
- S[i]가 '0'인 경우:
- 아직 등장한 '1'이 없다면(oneCount = 0), 해당 '0'은 그대로 두어도 되므로 다음 반복으로 건너뜁니다.
- 그렇지 않다면 flipCount를 1 증가시킵니다. (현재 '0'을 '1'로 뒤집는 비용)
- S[i]가 '1'인 경우 oneCount를 1 증가시킵니다.
- 만약 oneCount < flipCount라면, 지금까지 등장한 모든 '1'을 '0'으로 뒤집는 것이 더 유리하다는 뜻이므로 flipCount := oneCount로 갱신합니다.
- S[i]가 '0'인 경우:
- 반복이 끝나면 flipCount를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFlipsMonoIncr(string S) {
int n = S.size();
int flipCount = 0;
int oneCount = 0;
for(int i = 0; i < n; i++){
if(S[i] == '0'){
if(oneCount == 0) continue;
flipCount++;
} else oneCount++;
if(oneCount < flipCount) flipCount = oneCount;
}
return flipCount;
}
};
main(){
Solution ob;
cout << (ob.minFlipsMonoIncr("010110"));
}입력
"010110"
출력
2
동작 원리 정리
이 알고리즘은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적입니다. 문자열을 순회하면서 '1'이 등장한 이후에 나오는 '0'마다 두 가지 선택지 중 더 저렴한 쪽을 고르게 됩니다.
- 현재 '0'을 '1'로 뒤집기: 비용 1
- 지금까지 등장한 모든 '1'을 '0'으로 뒤집기: 비용 oneCount
if(oneCount < flipCount) 조건이 바로 이 두 선택지를 비교하는 부분입니다. 앞서 누적된 flipCount가 현재까지의 '1' 개수보다 많다면, 그동안의 뒤집기 전략을 버리고 '1'들을 모두 '0'으로 바꾸는 편이 더 적은 비용이 든다는 의미입니다. 이렇게 매 시점 최적의 선택을 누적해 나가면 최종적으로 최소 뒤집기 횟수를 얻을 수 있습니다.