[알고리즘 PS] 백준 1439번 뒤집기 자바 문제풀이

문제

해당 포스팅은 백준의 1439번 뒤집기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

1439번: 뒤집기

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

문제에서 문자열이 0과 1로만 이루어져 있다고 한다.

 

연속된 하나 이상의 숫자를 잡고 뒤집는다고 했는데, 이 글을 보고 든 생각이

 

연속된 하나의 숫자를 그냥 하나의 숫자로 만들어버리면 되겠다. 즉, 숫자간의 연속된 수의 중복을 없애면 되겠다.

였다.

 

그럼 만약 00011011001 이라는 수가 있다고 가정해보면 010101이 되는 것이다.

 

이제 0을 뒤집을지 1을 뒤집을지 결정할 수 있다.

 

그렇다. 1과 0중 등장한 횟수가 더 작은 것을 출력해주면 된다.

정답 코드

public class Main {
    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[] s = br.readLine().split("");
        int[] arr = new int[s.length];

        for (int i = 0; i < s.length; i++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]);
        int last = 0;
        for (int i = 1; i < arr.length; i++) {
            if(list.get(last) != arr[i]) {
                list.add(arr[i]);
                last++;
            }
        }

        int oneCount = 0;
        int zeroCount = 0;
        for(int value : list) {
            if(value == 1) oneCount++;
            else zeroCount++;
        }

        bw.write(String.valueOf(Math.min(oneCount, zeroCount)));
        bw.flush();
        bw.close();
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.