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

문제 1439번

1439번: 뒤집기

[ 문제 풀이 ]

연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이므로 0끼리, 1끼리 묶었을 때 더 적은 묶음의 개수를 찾으면 됩니다. 여러가지 간단한 방법들도 많지만, dfs로 탐색과 StringTokenizer 방법 2가지로 각각 풀어보았습니다.

[ 코드 ]

1) DFS 탐색
문자열을 순회하며 0을 만났을 때와 1을 만났을 때, 각각 res1, res2를 증가시키고 dfs()를 돌려 0의 묶음과 1의 묶음의 개수를 카운트해줍니다. 이 때, visit[]으로 각 인덱스의 방문 여부를 체크하여 중복 방문을 하지 않도록 해줍니다.

import java.io.*;

public class Main {
    private static String s;
    private static boolean[] visit;
    private static char[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        s = br.readLine();
        arr = new char[s.length()];
        visit = new boolean[s.length()];

        int res1 = 0;
        int res2 = 0;

        for (int i = 0; i < s.length(); i++) {
            arr[i] = s.charAt(i);
        }

        for (int i = 0; i < arr.length; i++) {
            if (visit[i]) continue;
            if (arr[i] == '0') {
                dfs(i);
                res1++;
            } else {
                dfs(i);
                res2++;
            }
        }

        bw.write(String.valueOf(Math.min(res1, res2)));
        bw.flush();
    }

    private static void dfs(int n) {
        if (n == s.length()-1) return;

        visit[n] = true;
        if (arr[n+1] == arr[n]) {
            dfs(n+1);
        }
    }
}

 

위의 코드로 실행한 결과입니다.

실행결과

 

 

2) StringTokenizer 이용

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

public class Main {
    private static String s;

	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();
        StringTokenizer st1 = new StringTokenizer(s, "0");
        StringTokenizer st2 = new StringTokenizer(s, "1");

        bw.write(String.valueOf(Math.min(st1.countTokens(), st2.countTokens())));
        bw.flush();
    }
}

 

위의 코드로 실행한 결과입니다. DFS 탐색을 활용한 방법보다는 살짝 느린 것을 확인할 수 있습니다.

실행결과