C++) 백준 11478번: 서로 다른 부분 문자열의 개수

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

11478번: 서로 다른 부분 문자열의 개수

감기 때문에 평소보다 머리도 안 돌아가고.. 고생고생해서 하나 풀고 자려 했는데 이게 웬걸 틀림... 그래도 힘내서 풀고 새로운 내용이라 포스팅까지 하자는 생각으로 글을 쓴다.

 

< 풀이 1 - map 이용 (시간 초과) >

사실 이거 왜 시간 초과가 떴는지는 모르겠다.

사고과정은 다음과 같다.

a, b, c, d, e

ab, bc, cd, de

...

이런 식으로 하나씩 map에 넣으면서 중복이 아닌 것만 세준다. 반복문도 하나인데 시간 초과 나옴.. 왜인지 모르겠다.

 

< 코드 >

#include <iostream>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

map<string, bool> mp;

int main()
{
string S;
cin >> S;

int i = 0, j = 1, count = 0;
string S_temp;
while (i <= S.length() - 1) {
if (i + j > S.length())
break;
S_temp = S.substr(i, j);
if (mp[S_temp] == true) {
if (i + j == S.length()) {
i = 0;
j++;
}
else {
i++;
continue;
}
}
else {
if (i + j == S.length()) {
i = 0;
j++;
mp[S_temp] = true;
count++;
}
else {
i++;
mp[S_temp] = true;
count++;
}
}
}

cout << count;

return 0;
}

 

< 풀이 2 - set 이용 (성공) >

사실 '중복을 허락하지 않는다.'를 떠올렸을 때 가장 처음 떠오르는 것은 '집합'이다. 근데 set은 지금까지 써본 적이 없어 map을 썼던 것인데 이번에 처음으로 써보기로 했다.

 

풀이과정은 위와 비슷한데 조금 다름.

위는 ababc를 예로 들면

a, b, a, b, c

ab, ba, ab, bc

...

이런 식으로 글자수가 하나씩 늘어가는 반면, 이번 풀이는 a, ab, aba, abab, ababc 이런 식으로 이중반복문을 사용하여 index를 하나씩 늘려가는 풀이다.

 

< 코드 >

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

set<string> st;

int main()
{
string S;
cin >> S;

string str = "";
for (int i = 0; i < S.size(); i++) {
for (int j = i; j < S.size(); j++) {
str += S[j];
st.insert(str);
}
str = "";
}

cout << st.size();

return 0;
}