[C++] 백준 16570번 앞뒤가 맞는 수열

문제

수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다.

(a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N

어떤 수열이 k-앞뒤수열일 때, k의 최댓값을 그 수열의 앞뒤계수라고 한다.

우리는 수열의 앞뒤가 맞게 만들기 위해 수열의 연속된 앞부분을 자를 수 있다.

예를 들어 (a1, a2, ⋯, aN) 에서 (a1, a2) 을 제거하면 (a3, a4, ⋯ , aN) 가 된다.

주어진 수열 (A1,A2, ⋯ , AN)의 앞부분을 얼마나 잘라야 앞뒤계수를 최대로 만들 수 있을까? 단, 그러한 방법은 2가지 이상일 수 있다. 그리고 자르는 방법에는 "아무것도 자르지 않는 것" 도 포함한다.

입력

첫 번째 줄에 N이 주어진다. (2 ≤ N ≤ 1,000,000)

두번째 줄에 N개의 정수 A1,A2, ⋯ , AN이 공백으로 구분되어 주어진다. (-231 ≤ Ai ≤ 231-1)

출력

앞부분을 잘라서 앞뒤수열로 만들 수 있다면, 그렇게 자른 후 수열의 앞뒤계수 최댓값과 그렇게 자르는 방법의 수를 공백으로 구분하여 출력한다. 어떻게 잘라도 앞뒤계수가 존재하지 않으면 -1 을 출력한다.

풀이

앞뒤수열이 앞수열과 뒤수열로 이루어진다고 하자.
수열의 앞에서부터 앞뒤수열을 찾으려하면 뒤수열이 시작할 지점을 지 정하기 매우 곤란하다.
하지만 뒤에서부터 앞수열의 끝나는 지점을 기준으로 앞뒤수열을 역으로 추적하면 뒤수열이 끝나는 지점은 항상 n-1이기 때문에 문제가 간단해진다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n;
int arr[1000000];
int cntLen[1000000];

void solve(){

  for (int i=n-2; i>=0; i--){
    int a = i;
    int b = n-1;
    int len = 0;

    while (arr[a] == arr[b]){
      a--;
      b--;
      len++;
    }

    cntLen[len]++;
  }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    cin >> arr[i];
  }

  solve();

  bool check = false;

  for (int i=n-1; i>=1; i--){
    if (cntLen[i]){
      cout << i << " " << cntLen[i];
      check = true;
      break;
    }
  }

  if (!check) cout << -1;

}