[백준] 1439번 : 뒤집기 – JAVA [자바]

[Silver V] 뒤집기 - 1439

문제 링크

성능 요약

메모리: 14284 KB, 시간: 124 ms

분류

그리디 알고리즘, 문자열

문제 설명

다솜이는 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. for문을 두개 돌려서 현재 값과 다음 인덱스의 값을 비교하며 수가 바꼈을 경우, 인덱스 값을 저장해둔다.
3. 첫 인덱스 값에서 저장한 인덱스 값 전까지를 substring()으로 받아서 바꿔준다. <불가능>

이런 식으로 하려 했으나 문제가 생겼다.

문제에서는 바꾸는 것이 아닌 바꾸는 최소 횟수를 구하는 것이다.
그리고 3번 과정이 가능하지 않다고 생각한다.

따라서 40분 고민한 후 해설을 보게 되었다.

---

• 해설

 

그리디 알고리즘은 최적의 해를 찾아 가는 것이므로, 여기선 입력 받은 문자열을 전부 0으로 바꾸는 경우(count0)와 1로 바꾸는 경우(count1), 총 2가지를 비교해서 최소 횟수를 출력하면 된다.

 

1. 문자열의 첫 번째 값이 0일 경우 나는 1로 바꿔줄 것이기 때문에 count1의 값을 1 증가한다. 
2. 반대의 경우인 첫 번째 값이 1일 경우 나는 0으로 바꿔줄 것이기 때문에 count0의 값을 1 증가한다.
3. 반복문을 돌리면서 현재 인덱스의 값과 다음 인덱스의 값을 비교한다.
4. 현재 인덱스 값과 다음 인덱스 값이 바뀔 때만 확인해주면 된다. 
5. 4의 과정에서 값이 바뀔 때, 다음 인덱스 값이 0일 경우와 1일 경우로 나눠 생각한다. (1, 2번 과정 동일)
6. count0과 count1의 최소를 출력한다.

---

• 코드

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

public class Main {
    public static void main(String[] args) throws IOException {

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

        String input = br.readLine();
        char[] data = input.toCharArray();
        
        // 전부 0으로 바꾸는 경우
        int count0 = 0;
        // 전부 1로 바꾸는 경우
        int count1 = 0;
        
        if(data[0] == '0')
            count1 += 1;
        else count0 += 1;

        for(int i = 0; i < data.length - 1; i++){
            if(data[i] != data[i+1]){
                // 다음 수에서 1로 바뀌는 경우
                if(data[i + 1] == '1'){
                    count0 += 1;
                    // 다음 수에서 0으로 바뀌는 경우
                }else count1 += 1;
            }
        }
        System.out.println(Math.min(count0, count1));
    }
}