[백준] 11478번: 서로 다른 부분 문자열의 개수

여기를 클릭하시면 문제를 볼 수 있습니다.

📕 문제 설명

📕 문제 풀이

제가 푼 방법은 다음과 같습니다.
입력 받은 문자열에서 부분 문자열을 생성하여 vector에 넣고 중복된 문자열(원소)을 삭제 후 vector의 길이를 구하여 서로 다른 부분 문자열의 개수를 구했습니다.

📕 Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
    string str;
    cin >> str;

    int len = str.size();
    int l = 1;
    vector<string> substr;
    
    while(len >= l)
    {
        for(int i=0; i<=len-l; i++)	
            substr.push_back(str.substr(i, l));		// 부분 문자열을 모두 생성하여 
            						//vector에 집어넣기
        l++;
    }

	// 중복제거
    sort(substr.begin(), substr.end());	
    substr.erase(unique(substr.begin(), substr.end()), substr.end());
    cout << substr.size() << '\n';	// vector의 길이는 곧 서로 다른 부분 문자열의 개수!

    return 0;
}

📕 관련 팁 (c++ 벡터 중복 제거)

c++에서 vector의 중복된 원소들을 제거하여 서로 다른 원소들이 하나씩만 존재하게 해야할 때는 다음과 같은 함수들을 사용하여 편리하게 할 수 있습니다.

[vector_name].erase(unique([vector_name].begin(), [vector_name].end()), [vector_name].end()); 

여기서 한가지 주의할 점은 이 방법을 사용하기 위해서는 먼저 vector의 원소들이 정렬 되어 있어야만 한다는 것입니다.

그러니 최종적으로는

sort([vector_name].begin(), [vector_name].end());
[vector_name].erase(unique([vector_name].begin(), [vector_name].end()), [vector_name].end()); 

이 되겠습니다.
( erase() 를 사용하기 위해서는 algorithm class를 선언해야 합니다. )