[C++] 백준 온라인 저지 1439번 뒤집기 풀이

0과 1로 이루어진 문자열을 몇 번 뒤집으면 모두 같은 숫자로 만들 수 있는지 구하는 문제

 

---

 

문제의 조건

 

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

 

입력

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

 

출력

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

 

 

풀이 과정

 

 예제랑 답을 보니까 연속된 같은 숫자 덩어리의 갯수를 구한 다음에 1과 0 덩어리 갯수 중 더 적은 것을 출력하면 될 거 같아서 코드로 짜 봤는데 통과했습니다.

 

1. 1과 0이 각각 연속된 덩어리의 갯수를 셀 변수 2개를 만든다. 연속된 덩어리를 저장하고 S 탐색 시 같은 숫자가 연속하고 있는지 아닌지 비교할 때 사용할 임시 string 변수도 하나 만든다. 

 

2. 반복문으로 S를 탐색하면서 현재 인덱스의 문자가 앞전 문자와 같으면 임시 string 변수에 저장하고 아니면 1과 0 카운터 변수 중 해당하는 카운터를 증가시키고 임시 string 변수를 초기화하고 이번 순서에 새롭게 바뀐 문자를 저장한다. 

 

3. 위 과정을 S의 마지막 인덱스까지 탐색하면서 반복한 후 1과 0 카운터 중 더 적은 값을 출력한다. 

 

 

코드

 

#include <iostream>
#include <string>

using namespace std;

int main(int argc, const char * argv[])
{
    string S;
    cin >> S;
    
    int oneCount = 0;
    int zeroCount = 0;
    string tmp = "";
    tmp += S[0]; //0번째 숫자만 저장하고 시작 
    for (int i = 1; S.length() > i; i++)
    {
        if (S[i] == tmp.back())
            tmp += S[i]; //같은 숫자가 연속하고 있으면 그냥 넘어감 
        else
        {
            //다른 숫자가 나오면 각각에 맞는 카운터를 증가시킨다.
            if ('0' == tmp.back())
                zeroCount++;
            else
                oneCount++;
            
            tmp = S[i]; //임시변수는 현재 순서 숫자로 바꾼다. 
        }
    }
    
    //위 반복문이 끝나기 직전에 마지막 숫자를 저장은 하지만 그에 대한 카운터 검사는 하지 않기 때문에 
    //마지막으로 저장된 숫자에 대해서 검사를 한 번 더 해준다. 
    if ('0' == tmp.back())
        zeroCount++;
    else
        oneCount++;
    
    //둘 중 더 적은 값 출력 
    cout << min(zeroCount, oneCount);
    
    return 0;
}