[BaekJoon] 1439 뒤집기 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

문제는 연속된 같은 수들을 뒤집어 모든 수를 0 또는 1로 만들 때 최소로 뒤집은 횟수를 구하는 문제이다.

이때 뒤집는 횟수는 연속된 같은 여러 장의 카드를 뒤집는 것을 1회 뒤집었다고 카운트하는 것이다.
즉, 000011에서 앞에 0000을 뒤집어 111111을 만드는 것은 1번 뒤집었다고 한다.

최소한의 뒤집는 횟수를 찾기 위해서는 모든 수를 0과 1로 뒤집을 때를 각각 계산하여 구해야 한다.

각각 0/1로 뒤집을 때는 같은 방법으로 계산을 하기에 모든 수를 0으로 뒤집을 때를 예시로 들고 설명을 하겠다.

모든 수를 0으로 만들려면 먼저 수열의 첫 번째 수를 확인하여 1일 경우 count 회수를 늘려줘야 한다. 그 후 i 번째 수와 i+1번째 수를 비교하며 값이 1에서 0으로 바뀔 경우는 다시 뒤의 0들을 1로 바꿔줘야 하기에 count를 하나 높여준다.

이런 식으로 0에 대한 count와 1에 대한 count를 구하여 둘 중 적은 값이 답이 된다.

👨🏻‍💻 작성한 코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		
		int count0 = 0; // 전부 0으로 만드는 경우
		int count1 = 0; // 전부 1로 만드는 경우
		
		// 첫째 문자에 따라 뒤집을 횟수 +
		if (str.charAt(0)=='0') count1++;
		else count0++;
		
		
		for(int i=0; i<str.length()-1; i++) {
			if (str.charAt(i) != str.charAt(i+1)) {
				if(str.charAt(i+1) =='0') count1++;
				else count0++;
			}
		}
		
		System.out.println(Math.min(count0, count1));
	}

}