777D Cloud of Hashtags

문제

• 링크 - http://codeforces.com/contest/777/problem/D

문제 분류

• 난이도 - 중
• 태그 - greedy, strings

문제 풀이

주어진 문자열들의 접미사들을 최소한으로 없애서 모든 문자열들이 사전순으로 정렬되어 있도록 하는 문제다.

연속된 두 문자열이 사전 순서로 되어야만 하므로, 두 문자열이 순서가 올바르지 않을때 무언가 조치를 취해야 한다. 다음과 같이 두 문자열의 순서가 잘못되었다고 해보자.

# a b d ..

# a b c ..

접미사를 없애야 하는데, 두 번째 문자열의 접미사를 어떻게 없애더라도 사전상으로 올바르게 할 수 없다. 무조건 첫 번째를 없애야 한다. 연속적인 두 문자열에 대해서 이렇기 때문에 모든 문자열에 대해서 확장해보면 가장 마지막 문자열부터 바로 이전 문자열의 접미사를 어떻게 잘라야할지 결정하면 된다는 것을 알 수 있다.

※ 한 문자열의 길이가 아니라 모든 문자열들의 길이가 500,000 이하이다.

소스 코드

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <bits/stdc++.h> using namespace std;   const int MAX_N = 5e5;   int n; string s[MAX_N];   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);       cin >> n;     for (int i = 0; i < n; i++) {         cin >> s[i];     }       int len[n];     len[n - 1] = s[n - 1].length();     for (int i = n - 2; i >= 0; i--) {         len[i] = 1;         for (int j = 1; j < len[i + 1]; j++) {             if (s[i][j] == s[i + 1][j]) {                 len[i]++;             } else if (s[i][j] < s[i + 1][j]) {                 len[i] = s[i].length();                 break;             } else {                 break;             }         }     }       for (int i = 0; i < n; i++) {         for (int j = 0; j < len[i]; j++) {             cout << s[i][j];         }         cout << '\n';     } }