앳코더90 - 006 - Smallest Subsequence（★5）

https://atcoder.jp/contests/typical90/tasks/typical90_f

006 - Smallest Subsequence（★5）

 

문제는 다음과 같다.

전체길이가 N인 문자열 S의

길이 K인 부분 문자열중 가장 빠른 사전순 문자열을 출력해라.

 

atcoder의경우

acd 이다.

 

이 문제를 봤을 때 dp 느낌으로 접근해야될것 같았고

K = 4 

zzzz 의 경우에는

모두를 선택해야되지만 앞에서부터 봤을때 index를 넘기면서 확인하는것이 불가능하다 판단해서

뒤에서 부터 개수를 세는 느낌으로 가야될 것같았는데

구체화를 못해서 에디토리얼을 보게되었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const int INF = 100000000;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;

int N, K;
string S;

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

    
    cin >> N >> K >> S;

    vector<vector<int> > res(N + 1, vector<int>(26, N));

    for (int i = N - 1; i >= 0; i--)
    {
        res[i] = res[i + 1];
        res[i][S[i] - 'a'] = i;
    }

    string ans = "";
    int idx = -1;

    for (int i = 0; i < K; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            int k = res[idx + 1][j];

            if (N - k >= K - i)
            {
                ans += (j + 'a');
                idx = k;
                break;
            }
        }
    }

    cout << ans;

    return 0;

}

 

중요한것은 res배열의 의미이다.

res[i][c]

i번 인덱스 이후 알파벳 c( a~ z )의 최초위치이다.

 

예시가 잘 나와있어서 그대로 가져왔다.

 

S = abca

nex[0][a] = 0
nex[0][b] = 1
nex[0][c] = 2
nex[0][d] = -1
nex[1][a] = 3
nex[1][b] = 1
nex[1][c] = 2
nex[2][a] = 3
nex[2][b] = -1
nex[2][c] = 2
nex[3][a] = 3
nex[3][b] = -1
nex[3][c] = -1

이렇게 전처리를 해놓고

K번 돌면서 길이 K인 문자열을 만드는데 

a~z 중 유효한 알파벳을 우선적으로 넣는것이다. 이를 res배열을 이용해서 판단하는 것이다.