[1257번] K번째 문자열

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN

알고리즘 분석 :

문제 해결에 필요한 사항

1. 트라이

2. Map STL

1. 트라이로 문제 해결을 할 수 있다.

트라이에 모든 값들을 넣어주고

순차적으로 a~z순으로 재귀적 탐색을 하면 정답을 얻을 수 있다.

이 문제에서는 부분집합 전체가 트라이에 들어가게 되니

하나의 노드를 방문할 때 마다 k가 1씩 감소하게 된다.

2. 간단히 map으로 해결 할 수 있다.

모든 값들을 다 넣어두고 맵을 돌며 k를 감소시켜 정답을 찾아낸다.

소스 코드 : 

#include <iostream>
using namespace std;
#define MAX_SIZE 26
 
struct Trie {
    Trie *next[MAX_SIZE];
    int isEnd;
 
    void init() {
        for (int i = 0; i < MAX_SIZE; i++)
            next[i] = nullptr;
        isEnd = false;
    }
};
 
Trie triePool[200000];
int trieIdx;
char str[402];
char tmp[402];
int k;
char nowStr[402];
char ans[402];
 
Trie *trieAlloc() {
    return &triePool[trieIdx++];
}
int _strlen(char * str) {
    int len = 0;
    while (str[++len]);
    return len;
}
void _strcpy(char *str1, char *str2, int s, int e) {
    int idx = 0;
    while (s <= e)
        str1[idx++] = str2[s++];
    str1[idx] = '\0';
}
 
void search(Trie *cur, int nowIdx) {
    if (k == 0) {
        _strcpy(ans, nowStr, 0, nowIdx - 1);
        return;
    }
    
    for (int i = 0; i < MAX_SIZE; i++) {
        int ch = i;
        if (cur->next[ch] && k > 0) {
            nowStr[nowIdx++] = ch + 'a';
            nowStr[nowIdx] = '\0';
            k--;
            search(cur->next[ch], nowIdx);
            nowStr[--nowIdx] = '\0';
        }
 
    }
}
void init() {
    trieIdx = 0;
    triePool[0].init();
}
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        init();
        scanf("%d", &k);
        scanf("%s", str);
 
        char none[] = "none";
        _strcpy(ans, none, 0, 3);
 
        Trie *root = trieAlloc();
 
        // insert
        int len = _strlen(str);
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                _strcpy(tmp, str, i, j);
 
                Trie *cur = root;
                int tLen = _strlen(tmp);
 
                for (int k = 0; k < tLen; k++) {
                    int ch = tmp[k] - 'a';
                    if (!cur->next[ch]) {
                        cur->next[ch] = trieAlloc();
                        cur->next[ch]->init();
                    }
                    cur = cur->next[ch];
                }
                cur->isEnd = true;
            }
        }
 
        search(root, 0);
        printf("#%d %s\n", tc, ans);
    }
 
    return 0;
}

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 41 42 43 44 45

#include <iostream> #include <algorithm> #include <map> #include <string>   using namespace std;   map<string, int> mp;   int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         int k;         scanf("%d", &k);         mp.clear();           string str;         char tmp[402];         scanf("%s", tmp);         str = tmp;           int len = str.size();         for (int i = 0; i < len; i++)             for (int j = 1; j <= len - i; j++)                 mp[str.substr(i, j)] = 1;           bool chk = false;         for (auto it = mp.begin(); it != mp.end(); it++, k--) {             if (k == 1) {                 printf("#%d %s\n", tc, it->first.c_str());                 chk = true;                 break;             }         }           if (!chk)             printf("#%d none\n", tc);     }       return 0; }   Colored by Color Scripter

cs