[C++] SWEA 1257번: K번째 문자열 (set 활용)

🔗 문제

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

SW Expert Academy

 

🖍 풀이

set 라이브러리의 특성을 이용하면 쉽게 풀 수 있다.

set은 중복을 제외하고, 오름차순으로 자동 정렬해주는 특성이 있다.

---

먼저 문자열을 다 쪼개어서 저장해준다.

substr(i, j)

i 위치에서부터 j개를 자르는 substr 함수

for(int i=0; i<str.size(); ++i)
{
    for(int **j=1**; **i+j<=str.size()**; ++j)
    {
        set.insert(str.substr(i, j));
    }
}

j는 공백을 빼기 위해서 0이 아니라 1부터 시작하고 원문의 사이즈를 넘지 않도록 i+j < str.size() 조건을 걸어주었다.

 

 

love를 예로 들었을 때 반복문마다 저장되는 값

i=0 → {l, lo, lov}
i=1 → {o, ov, ove}
i=3 → {v, ve}
i=4 → {e}

눈치 챘을지 모르겠지만 love 원문이 빠져있다. 따로 삽입해주었고 혹시 모를 공백도 제거했다.

 

set.insert(str);
set.erase("");

set은 자동으로 오름차순 정렬해주기 때문에 이터레이터를 이용해서 N번째를 출력만 해주면 된다.

 

💾  소스

#include <iostream>
#include <string>
#include <vector>
#include <set>

int main()
{
    int T, N;
    std::string str, answer;
    
    std::cin >> T;
    for(int tc=1; tc<=T; ++tc)
    {
        std::cin >> N >> str;
        std::set<std::string> set;
        
        for(int i=0; i<str.size(); ++i)
        {
            for(int j=1; i+j<=str.size(); ++j)
            {
                set.insert(str.substr(i, j));
            }
        }
        
        set.insert(str);
        set.erase("");
        
        if(set.size() < N)
            answer = "none";
        else
        {
            auto iter = set.begin();
            for(int i=0; i<N; ++i)
            {
                iter++;
            }
            answer = *(--iter);
        }
        
        //output
        std::cout << '#' << tc << ' ' << answer << '\\n';
    }
    return 0;
}