[백준 01639] 행운의 티켓 [Java]

문제

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

---

풀이

주어진 문자열 S에 대해 2N자리의 부분 문자열의 각 자리를 더했을 때 왼쪽과 오른쪽 N자리의 합이 동일한 부분 문자열의 최대 길이를 구하는 문제다.

우선 S의 길이에 따라 가능한 최대 크기를 정해주자.

홀수면 1을 빼고, 짝수면 원래 크기 그대로 최대 크기가 될 수 있다.

        // Solve
        int GAP = nums.length % 2 == 0 ? nums.length : nums.length - 1;

길이가 홀수인 정답은 없으므로 GAP이 0이 될 때 까지 2씩 감소시키며 문제의 조건을 만족시키는 부분 문자열을 찾으면 된다.

        while (GAP > 0) {
            for (int i = 0; i + GAP <= nums.length; ++i) {
                if (check(i, i + GAP)) {

                    // Output
                    System.out.println(GAP);
                    return;
                }
            }
            GAP -= 2;
        }

check에서는 왼쪽/오른쪽 N자리의 합을 더하고 빼서 결과가 0이 되는지에 따라 참/거짓을 반환한다.

    private static boolean check(int L, int R) {
        final int MID = (L + R) >> 1;
        int sum = 0;
        for (int j = L; j < MID; ++j) {
            sum += nums[j] - '0';
        }
        for (int j = MID; j < R; ++j) {
            sum -= nums[j] - '0';
        }
        return sum == 0;
    }

만약 GAP이 0이 되어도 결과를 출력하지 못했다면 문제의 조건을 만족하는 부분 문자열을 찾지 못한 것 이므로 0을 출력하면 된다.

        System.out.println(0);
    }
}

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/01639.java

problem-solving/baekjoon-online-judge/easy/01639.java at main · rogi-rogi/problem-solving