728x90
쉬운문제였는데...
시간초과때문에 조금 오래 생각했다ㅋ..
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로 만들었다.
시간복잡도에 대해 잘 고민해볼 필요가 있어보인다.
728x90
'코테준비 > 하루한개도전~' 카테고리의 다른 글
백준 : 20164 - 홀수 홀릭 호석 (0) | 2024.07.10 |
---|---|
백준 : 19951 - 태상이의 훈련소 생활 (0) | 2024.07.10 |
atcoder : B - Interactive Sorting (0) | 2024.07.07 |
swea : 1206 - View (1) | 2024.07.02 |
프로그래머스 : DFS/BFS - 네트워크 (1) | 2024.07.02 |