[백준] S5 1439번 뒤집기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1439번: 뒤집기

[문제] 

다솜이는 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. 뒤집어야하는 최소 횟수는 문자의 숫자가 몇 번 바뀌는지 체크 후, 바뀐 횟수 / 2를 해주면 된다.

2. 문자가 몇번 바뀌는지 체크하기 위한 변수를 주고 비교하며 몇 번 바뀌었는지 체크해준 후 결과를 출력해주면 된다.

[접근]

1. 문자를 최소 몇 번 뒤집어야 하는지 생각을 해 보았다.

2. 문제에서 주어진 테스트 케이스를 확인해보니 생각한 식(바뀐 횟수 / 2)이 맞아 해당 식을 사용해서 문제를 해결하였다.

[코드]

package BOJ_silver;

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

public class Main_S5_1439 {
	static int cnt = 1; // 문자가 변경되는 횟수, 처음에 무조건 나오니까 1
	static char check; // 문자가 변경되는지 체크할 문자
	static String str; // 입력받을 문자열
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 문자열 입력받기
		str = br.readLine();
		// 맨 처음 문자를 비교한 문자로 두기
		check = str.charAt(0);
		
		for (int i = 1; i < str.length(); i++) {
			// 문자가 다르면 cnt 증가시키고 비교 문자를 현재 문자로 변경
			if (str.charAt(i) != check) {
				check = str.charAt(i);
				cnt++;
			}
		}
		
		// cnt / 2가 바꿔야 하는 최소 횟수
		System.out.println(cnt / 2);
	}
}