[백준] BJ 16570. 앞뒤가 맞는 수열(Java)

문제

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

 

풀이

KMP 알고리즘을 사용하는 문제입니다.

입력 값을 역순으로 arr 배열에 담고 이를 바탕으로 테이블을 형성해줍니다.

(sb.reverse().toString()으로 넘겨주고, s.charAt(i)를 이용해서 풀면 예제만 맞고 3%에서 틀림..)

 

형성한 테이블의 인자 값들은 i번째 인덱스까지의 연속 부분수열의 길이의 최댓값을 의미합니다.

따라서 테이블값을 순회하며

1) table[i]가 기존에 저장된 값(length = 0 초기화)보다 클 경우, res를 table[i] 및 cnt = 1(몇 번 반복했는지)로 갱신해줍니다.

2) table[i]가 기존에 저장된 값과 같을 경우, table[i] == res라면 cnt를 ++해줍니다.

 

순회를 마치고

res 값이 0이라면 -1을 출력하고, 이외의 케이스는 res와 cnt를 출력합니다.

 

코드

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

public class Main {
    static int N;
    static int[] table, arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        // 테이블 생성
        table = new int[N];
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = N - 1; i >= 0; i--) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        makeTable();

        int res = 0, cnt = 0;
        for (int i = 0; i < N; i++) {
            if (table[i] > res) {
                res = table[i];
                cnt = 1;
            }
            else if (table[i] == res)
                cnt++;
        }
        if (res == 0)
            System.out.println(-1);
        else
            System.out.println(res + " " + cnt);
    }

    public static void makeTable() {
        int idx = 0;
        for (int i = 1; i < N; i++) {
            while (idx > 0 && arr[idx] != arr[i]) {
                idx = table[idx - 1];
            }
            if (arr[idx] == arr[i]) {
                table[i] = ++idx;
            }
        }
    }
}