13013번: 접미사 배열 2

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


$O(n)$

입력으로 주어진 접미사 배열: a[0...n-1]
구하고자 하는 문자열: s[0...n-1]
아래에서 문자 혹은 문자열간 크기 비교시 작다는 것은 사전순으로 빠름을 의미함.

다음 성질들을 만족한다.
1. 임의의 i, j에 대해 s[a[i]...n-1] < s[a[j]...n-1] <-> 임의의 i에 대해 s[a[i]...n-1] < s[a[i+1]...n-1]
2. 임의의 i에 대해 s[a[i]] <= s[a[i+1]]

따라서 s[a[i]] < s[a[i+1]]를 만족하는 i의 개수가 가능한 작아야 하며,  이 값+1이 답이다.

s[a[i]] < s[a[i+1]]를 무조건 만족해야하는 경우는 그 다음 문자들로 구성된 문자열간의 관계가 s[a[i]+1...n-1] > s[a[i+1]+1...n-1]인 경우이다.(빈 문자열은 사전순으로 가장 빠르다고 가정)
또한 이 문자열간 크기 관계는 주어진 접미사 배열로 확인할 수 있다.

#include<cstdio>
int a[50], b[51], n, r = 1;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), b[a[i]] = i + 1;
    for (int i = 1; i < n; i++) r += b[a[i - 1] + 1] > b[a[i] + 1];
    printf("%d", r);
    return 0;
}