백준 1639: 행운의 티켓[JAVA]

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

1639번: 행운의 티켓

 

[난이도]

- Silver 4

 

[알고리즘]

- 구현

- 부르트 포스

 

[코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String S = br.readLine();

        int N = 0;
        int answer = 0;
        for (int i = 1; i <= S.length() / 2; i++) { // (S의 길이 / 2)만큼 반복
            N = i * 2; // N은 2의배수로 증가함
            for (int j = 0; j < S.length() - N + 1; j++) { // (S의 길이 - N + 1)만큼 반복
                String tmp = S.substring(j, j + N); // 문자열을 j부터 j+N 만큼만 추출
                if (StringSum(tmp.substring(0, N / 2)) == StringSum(tmp.substring(N / 2))) { // 각 자리수를 더한 값이 같다면 true
                    answer = N; // answer 는 현재 확인하는 문자열의 길이 N
                    break; // 이미 answer를 찾았다면 더이상 할 필요가 없기 때문에 break;
                }
            }
        }
        System.out.println(answer);

        br.close();
    }

    static int StringSum(String s) { // 각 자리수를 더한 값을 반환
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += s.charAt(i) - '0';
        }
        return sum;
    }
}

 

[풀이]

부르트 포스 문제인줄알고 풀었지만 풀다보니 그냥 구현문제 같다. break로 반복문을 탈출하기 때문에 부르트포스 같지 않다.

1. 입력받은 (문자열의 길이 / 2) 만큼 반복한다. 문자열을 2N만큼 잘라서 확인하기 때문에 이렇게 제한을 두지 않으면 인덱스를 넘어가 오류가 발생한다.

2. 문자열을 2N만큼 잘라서 확인 후 좌, 우를 나눠 각 자리수의 합을 구한다. 좌, 우의 합이 같을 경우 answer을 N으로 초기화해준다.

 

다 풀고보니 시작을 2부터시작해 2, 4, 6, 8 ... 이런식으로 하는것보다 큰 수부터 ... 8, 6, 4, 2 이렇게 푸는게 시간이 더 적게 걸릴것 같다.