[BOJ/1439/C++] 뒤집기

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

문제

• 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

조건

• 첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

SOL

이 문제는 모든 경우를 뒤집어보는 브루트포스를 이용하려면 이중For을 이용해야하는데, S가 100만이므로 O(N^2)은 사용할 수가 없다. 즉, 다른 방법을 이용해서 최소한의 횟수를 찾아내야한다.

문제를 보면, 결국은 앞면 /뒷면 2가지경우의 수 이므로, 연속된 "0"의 갯수와 연속된 1의 갯수의 묶음 중, 작은걸 출력하면 된다. 뒤집고 , 또 뒤집는 경우는 어쨋든 한번의 행위가 더 들어가므로, 처음부터 최소한으로 뒤집는것이 Best Practice이다.

만약, s[i]와 s[i+1]이 다르면서, s[i]가 '0'이라면, 이 숫자는 0의 연속된 묶음이다.
그렇지만, s[i]가 1이라면 이 숫자는 1의 연속된 묶음이다. 나누어준 뒤, 둘 중 작은 값을 출력하면된다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main()
{
  fastio;
  string s;
  cin >> s;
  // zero_cnt,one_cnt
  int zero_series = 0;
  int one_series = 0;
  for (int i = 0; i < s.length(); i++)
  {
    if (s[i] != s[i + 1] && s[i] == '0')
    {
      zero_series++;
      continue;
    }
    if (s[i] != s[i + 1] && s[i] == '1')
      one_series++;
  }
  cout << min(zero_series, one_series) << '\n';
  return 0;
}