SWEA 1257 K번째 문자열 C++

문제: SW Expert Academy 1257 K번째 문자열

 

swea에서 문자열 매칭 강의를 듣고 이 문제를 풀게 되는 사람들이 많을텐데, 강의에서 접미어 배열, 트라이, kmp 등등의 고급(?) 알고리즘이 등장한 것에 비해서 꽤나 쉽게 풀리는 문제이다.

 

굉장히 단순하게 주어진 문자열을 자를 두 위치를 i와 j로 지정하고, 파생되는 있는 모든 경우의 부분 문자열을 생성한다.

 

그리고 이 부분 문자열들을 저장할 컨테이너가 필요한데, 예시로 주어진 것처럼 food의 경우 o라는 부분 문자열이 중복(2번) 발생할 수 있다.

 

여기서 중복을 제거하기 위해서 set을 써야함을 눈치챌 수 있었다면 굉장히 쉽게 풀 수 있다.

 

특히나 해당 문제는 "k번째" 부분 문자열 출력을 위해서 정렬이 필요한데, set을 쓸 경우 삽입과 동시에 정렬이 일어나기 때문에 set을 사용하는 것은 합리적인 선택이라고 할 수 있다.

 

따라서 이 문제를 풀기 위해서는 set과 관련된 삽입, 조회, 반복자 이용 등에 익숙해질 필요가 있다.

 

모든 문자열을 생성한 후 set에 들어있는 원소의 개수가 k보다 작다면 k번째 원소를 출력할 수 없으므로 none을 출력하고, 그렇지 않다면 반복자(iterator)를 k만큼 이동시켜서 k번째 원소를 출력할 수 있도록 한다.(set에서 원소 출력을 위해서 이런 방법 밖에 없는지, 더 효율적인 방법이 있는지에 대해서는 추가적인 학습을 진행할 예정)

 

/* SWEA 1257 K번째 문자열 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <set>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int t, T, k;
string str;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> T;
    for (t = 1; t <= T; t++)
    {
        cin >> k >> str;
 
        set<string> s; // 집합 // 삽입과 동시에 정렬됨
 
        for (int i = 0; i < str.length(); i++)
            for (int j = 0; j < str.length(); j++)
                s.insert(str.substr(i, j + 1)); // 모든 부분 문자열들을 삽입
 
        cout << "#" << t << ' ';
        if (s.size() < k) // K번째 원소가 없는 경우 none 출력
            cout << "none" << endl;
        else
        {
            set<string>::iterator iter = s.begin(); // 첫번째 원소 가리키는 반복자
            for (int i = 0; i < k - 1; i++)
                iter++; // 집합에서 K번째 원소 출력
            cout << *iter << endl;
        }
    }
 
    return 0;
}