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

쉬운문제였는데...

시간초과때문에 조금 오래 생각했다ㅋ..

https://www.acmicpc.net/problem/11478

---

그냥 substr 전부 뽑아서, 중복을 제거해주면 된다.

 

이 때 중복을 제거할 때 조금 생각을 해야하는데

일단 substr뽑을때 반복문을 한번 돌고, 그 안에서 중복비교를 위해 find를 계속해서 해주는데 이 과정에서 또 list를 한번 돈다

-> 이런식으로 매번 전부 비교하면, 너무 시간복잡도가 커지게된다!

 

=> 일단, 반복문 한번 돌면서 substr을 전부 뽑아준다 (중복 신경xx)

=> 그리고 substr들을 사전순으로 정렬해준다! (그냥 sort써주면 알아서 정렬해준다)

=> 사전순으로 정렬됐으니까, 인접한 문자열끼리 비교해서 중복을 제거해준다 (반복문 한번만 돌면 됨)

=> 최종적으로 길이가 n인 substr을 확인할 때, 시간복잡도가 위에보다 적어진다!

 

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

using namespace std;

vector<string> get_subset2(string text){
    // s보다 길이가 1 작은 subset을 리턴, 중복제거
    // => 무조건 2개만 나옴!
    vector<string> result;
    int size = (int)text.size();
    
    string left = text.substr(0, size-1);
    string right = text.substr(1, size-1);
    result.push_back(left);
    if(left.compare(right) == -1){
        // 다름
        result.push_back(right);
    }
    return result;
}

int get_subset_count(string text, int size){
    // 중복을 제거한채로 반환해주기!
    vector<string> result;
    
    for(int i = 0; i<(text.size()-size+1); i++){
        string now = text.substr(i, size);
        result.push_back(now);
    }

    // 사전순 정렬
    sort(result.begin(), result.end());

    // 중복 체크 -> 사전순으로 인접한것끼리만 비교하면 된다
    string prev = result[0];
    int result_count = 1;
    for(int i = 1; i<result.size(); i++){
        if(prev.compare(result[i]) != 0){
            // 중복이 아님
            result_count++;
            prev = result[i];
        }
    }


    return result_count;
}


int main(){

    //string text = "ababc";
    string text;
    cin>>text;
    int size = text.size();

    int answer = 1; // text그대로인 subset은 항상 포함

    for(int i = size-1; i>0; i--){
        answer += get_subset_count(text, i);
    }



    cout << answer << endl;

    return 0;
}

 

이 때 중복체크할때 굳이 vector를 건드릴 필요없이, 개수만 필요해서 그냥 count로 만들었다.

 

---

시간복잡도에 대해 잘 고민해볼 필요가 있어보인다.