[백준OJ] 1439번 뒤집기

https://www.acmicpc.net/problem/1439

1439번: 뒤집기

---

 

-풀이-

0의 뭉텅이의 개수와 1의 뭉텅이의 개수를 구해준 뒤 , 개수가 더 작은쪽의 개수만큼을 뒤집어주면 모두 같은수가 된다.

 

-시간복잡도-

문자열의 길이를 N이라고 한다면, 문자열 한번만 탐색하면되므로, O(N)이 된다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

string str;
int zero, one;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	zero = one = 0;

	cin >> str;
	char flag = str[0];
	for (int i = 1; i < str.length(); i++) {
		if (flag != str[i]) {
			if (flag == '0') {
				zero++;
			}
			else if(flag=='1'){
				one++;
			}
			flag = str[i];
		}
	}
	if (flag == '0') {
		zero++;
	}
	else if (flag == '1') {
		one++;
	}
	cout << min(zero, one);
	return 0;
}