[BaekJoon] 1439 뒤집기

1.  문제 링크

2.  문제

요약

• 0과 1로만 이루어진 문자열에서 연속된 하나 이상의 숫자를 뒤집어서, 즉 0은 1로 1은 0으로 만들어서 모두 같은 숫자로 만드려고 할 때 최소로 뒤집는 횟수를 구합니다.
• 입력: 0과 1로만 이루어진 문자열 S가 주어집니다.
• 출력: 최소로 뒤집는 횟수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int reverse(String input) {
		String allOne = "";
		String allZero = "";
		for(int i = 0; i < input.length(); i++) {
			allOne += "1";
			allZero += "0";
		}
		if(input.equals(allOne) || input.equals(allZero)) {
			return 0;
		}
		int[] count = new int[2];
		for(int i = 1; i < input.length(); i++) {
			if(input.charAt(i - 1) != input.charAt(i)) {
				if(input.charAt(i - 1) == '0') {
					count[0]++;
				} else {
					count[1]++;
				}
			}
			if(i == (input.length() - 1)) {
				if(input.charAt(i) == '0') {
					count[0]++;
				} else {
					count[1]++;
				}
			}
		}
		if(count[0] > count[1]) {
			return count[1];
		} else {
			return count[0];
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.reverse(input) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 문자열 S에 있는 모든 숫자를 0 또는 1로 만들 때, 연속으로 0이 나오는 부분과 연속으로 1이 나오는 부분의 개수를 세서 그 중 더 작은 개수가 최소로 뒤집는 횟수가 됩니다.
• 예를 들어 11001100110011000001 문자열이 주어졌을 때, 0이 연속되는 부분의 개수는 00, 00, 00, 00000으로 총 4개이고 1이 연속되는 부분의 개수는 11, 11, 11, 11, 1으로 총 5개이기 때문에 최소로 뒤집는 횟수는 4입니다.
• 주어진 숫자는 0 또는 1로 2개이고 같은 숫자로 연속되어 있는 것은 같이 뒤집을 수 있으므로 0이 연속되는 부분을 모두 1로 바꾸는 방법이나 1이 연속되는 부분을 모두 0으로 바꾸는 방법으로 모두 같은 숫자로 만들텐데 그렇다면 더 작은 횟수로 뒤집기 위해서는 더 작은 개수를 갖고 있는 것을 뒤집는 것이 최소로 뒤집는 횟수가 될 것입니다.