11059 크리 문자열 ⬛

📋문제 정리

• 숫자로만 이루어진 문자열의 부분 문자열이 짝수고 절반의 앞과 뒤의 합이 같으면 크리 문자열이다.
• 6789 6789 / 6 789 789 이런식으로 되어있는데 가장 길이가 긴 크리 문자열의 길이를 출력하라.

🎯풀이

• 크리 문자열이기 위해서는 무조건 답은 짝수로 나와야한다. 2/4/6/8...
• 짝수칸 만큼 잡아서 비교를 해야한다.
• 짝수 칸을 잡았다면 절반의 앞의 합과 뒤의 합을 비교 후 같으면 잡은 칸의 길이를 저장한다.
• 누적 합 배열을 사용해서 뒤의 합 - 절반 과 앞의 합 - 시작점을 비교하면 된다.

  index가 0 12 / 34 라면 4칸, 2는 0,1,2의 합 - 0을 하면 1,2의 합 구할 수 있고
  4는 0,1,2,3,4의 합 4 - 2는 3,4의 합, 절반인 2의 앞의 합과 뒤의 합을 비교할 수 있다.

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

public class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st;
  static StringBuilder sb =  new StringBuilder();

  public static void main(String[] args) throws IOException {
    String str = br.readLine();
    int ps[] = new int[str.length()+1]; // 누적 합 배열 생성 0의 값은 항상 0
    int result=0;
    
    for(int i=0;i<str.length();i++){
      ps[i+1] = ps[i] + (str.charAt(i)-'0'); // 누적 합 배열 초기화
    }

    for(int i=2;i<=str.length();i+=2){ // 짝수 칸 만큼 잡음
      for(int j=0;j+i<=str.length();j++){ //잡은 칸에서 index를 1씩 높여가며 탐색
        int mid = j+i/2;
        int end = j+i;

        int sum1 = ps[mid] - ps[j];  //절반앞의 합 - 시작점
        int sum2 = ps[end] - ps[mid]; //뒤의 합 - 절반 앞의 합
		
        if(sum1 == sum2)
          result = i;

      }
    }

    sb.append(result);
    System.out.println(sb);
    br.close();
  }
}