[BaekJoon] 11565 바이너리 게임 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static String startStr;
    static String endStr;

    static void input() {
        Reader scanner = new Reader();

        startStr = scanner.nextLine();
        endStr = scanner.nextLine();
    }

    /*
     * 이 문제에서 할 수 있는 작업은 a의 맨 앞에 있는 문자를 빼거나 a의 맨 뒤에 parity(a)를 추가하는 작업이다
     * 그런데 parity(a)는 문자열 a의 1의 개수에 따라 값이 바뀌고, 1의 개수가 홀수개라면 1, 1의 개수가 짝수개라면 0이 된다
     *  -> 즉, 1의 개수가 홀수개여야만 1을 추가할 수 있다!
     *  -> 그렇다면 홀수개에서 1을 추가하면 1의 개수가 짝수개가 되고, 더이상 1을 추가할 수 없다!
     *  -> 즉, 1의 개수는 기존 개수에서 최대 1 증가할 수 있다!
     *
     * 그러므로 a의 1의 개수가 b의 1의 개수보다 크거나 같으면 parity(a)를 추가하고 맨 앞에 있는 문자들을 제거하며 b를 만들 수 있다!
     * 만약 a의 1의 개수가 b의 1의 개수보다 작을 경우, a의 1의 개수가 홀수개이고 b의 1의 개수보다 1개 작다면 a에 parity(a)를 추가하여 b의 1의 개수와 맞출 수 있다
     *  -> 그렇기 때문에 이 경우에도 a를 b로 변경할 수 있다!
     * 위 두 가지의 경우를 제외하고는 a를 b로 변경할 수 없다.
     * 즉, 아래와 같다
     *  1) a >= b || (a % 2 == 1 && a + 1 == b) => VICTORY
     *  2) else ... DEFEAT
     *
     * 위 조건은 아래와 같이 간략화할 수 있다
     *  (a + 1) / 2 >= (b + 1) / 2 => VICTORY
     *  else... DEFEAT
     *      -> a의 1의 개수가 b의 1의 개수보다 크거나 같다면 위 수식은 참이 된다
     *      -> a의 1의 개수가 홀수 개이고 b의 1의 개수보다 1 작다면 위 수식은 참이 된다
     *      -> 그렇지 않은 경우는 위 수식이 거짓이 된다
     */
    static void solution() {
        int startStrOneCount = findOneCount(startStr);
        int endStrOneCount = findOneCount(endStr);

        if ((startStrOneCount + 1) / 2 >= (endStrOneCount + 1) / 2) {
            System.out.println("VICTORY");
        } else {
            System.out.println("DEFEAT");
        }
    }

    static int findOneCount(String str) {
        int oneCount = 0;
        for (int idx = 0; idx < str.length(); idx++) {
            if (str.charAt(idx) == '1') {
                oneCount++;
            }
        }

        return oneCount;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}