[Baekjoon] 1439번: 뒤집기 - Java

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

1439번: 뒤집기

문제 설명

문제는 복잡하지 않다. 0 또는 1로 이루어진 문자열이 주어진다. 그리고 연속된 하나 이상의 숫자를 뒤집을 수 있으며 모두 같은 숫자를 만들어야 한다. 이때 뒤집는 최소 횟수를 출력하면 된다.

풀이 방법

잠깐 생각해보면 금방 풀이를 떠올릴 수 있을 것이다. 연속된 숫자를 뒤집어야 하기 때문에 연속된 숫자가 적은 숫자를 뒤집으면 된다. 예를 들어 보자.

10110001이 주어졌다. 연속된 하나 이상의 숫자를 뒤집는 최소 횟수를 구해야 하기 때문에 0을 2번 뒤집으면 될 것이다.

01010101이 주어졌다. 0과 1의 수가 같으므로 무얼 뒤집든 4번 뒤집으면 된다.

이런 식으로 0과 1중 연속된 숫자가 적은 수를 뒤집으면 문제를 해결할 수 있다.

코드

package baekjoon.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ1439 {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] input = br.readLine().toCharArray();

        int countForZero = 0;
        int countForOne = 0;
        char prev = '0';

        // 첫 번째 숫자를 체크하기 위한 if 문
        if (input[0] == '1') {
            countForOne = 1;
            prev = '1';
        } else {
            countForZero = 1;
            prev = '0';
        }

        for (int i = 1; i < input.length; i++) {
            char current = input[i];
            /* 
             * 현재 숫자가 이전 숫자와 같으면 다음 숫자로 넘어가고
             * 다르면 연속되지 않았다고 판단하고 카운트를 증가시킨 후
             * 이전 숫자를 현재 숫자로 변경한다.
             */
            if (current != prev) {
                if (current == '0') {
                    countForZero += 1;
                } else {
                    countForOne += 1;
                }
                prev = current;
            }
        }

        int result = countForZero > countForOne ? countForOne : countForZero;

        System.out.println(result);

    }
}