[백준] 1439 뒤집기 - Greedy / Java

• 문제 링크

1439번: 뒤집기

 

• 풀이 과정

예제 입력 4를 예시로 들자면,

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1

1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1

1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

위와 같이 부분적으로 뒤집어 점진적으로 뒤집는 크기를 늘려갈 때 최소 4회에 걸쳐 뒤집을 수 있다.

하지만 이는 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 와 같이 단순히 연속된 토큰을 뒤집는 것과 4회로 횟수가 같다.

 

따라서 StringTokenizer 를 활용하여 연속된 1의 토큰 수와 0의 토큰 수 중 작은 값을 구해 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

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();

        StringTokenizer one = new StringTokenizer(s, "0");
        StringTokenizer zero = new StringTokenizer(s, "1");

        bw.write(String.valueOf(Math.min(one.countTokens(), zero.countTokens())));
        bw.flush();
    }

}

 

아래는 StringTokenizer 대신 직접 구현한 코드이다.

성능에선 근소하게 나마 앞섰지만 같은 수준이라고 보아도 무방했다.

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

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));

        char[] arr = br.readLine().toCharArray();

        int one = 0;
        int zero = 0;

        if (arr[0] == '1')
            one++;
        else
            zero++;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] != arr[i]) {
                if (arr[i] == '1')
                    one++;
                else
                    zero++;
            }
        }

        bw.write(String.valueOf(Math.min(one, zero)));
        bw.flush();
    }

}