[백준 BOJ] 11478 서로 다른 부분 문자열의 개수 C++

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

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

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

---

문제

예제

• 문제해석 및 풀이

 이 문제는 문자열 하나를 입력받은 후 그 문자열의 중복을 허용하지 않는 부분 문자열의 개수를 구하는 문제이다. '중복을 허용하지 않는다'에서 생각나는 것이 있다. 바로 set이다. set은 중복을 없앤다. 따라서 적절하게 문자열을 분해해서 set으로 선언한 객체에 넣어주고 그 객체의 크기를 구하면 서로 다른 부분 문자열의 개수를 구할 수 있다.

• 코드

 

#include <iostream>
#include <set>
using namespace std;

int main() {
	string str;
	string tmp = "";
	cin >> str;
	set<string> partial;
	for (int i = 0; i < str.size(); i++) {
		for (int j = i; j < str.size(); j++) {
			tmp += str[j];
			partial.insert(tmp);
		}
		tmp = "";
	}
	cout << partial.size();
	return 0;
}

 이 코드에서 볼만한 것은 이중반복문에서 tmp변수를 초기화를 해 주어야 한다는 것이다. tmp변수는 partial객체에 입력을 넣어주기 위해 임시로 선언한 변수이기 때문에 다음 루프가 돌기 전에 초기화를 해 주어야 올바른 값을 넣어줄 수 있다.

• 정리

 set을 이용하지 않고 중복을 없애는 방법을 이용해 벡터나 문자열을 통해 풀 수 있을 것 같지만 set을 이용해서 푸는 것이 더 간편할 것 같다. 그리고 이 문제를 풀다가 문자열의 일부분을 추출하는 substr함수에 대해서 알게 되어서 이 함수를 쓰려고 했으나 틀렸다... substr함수에 대한 이해가 부족했던 것 같다. 다음에는 이 함수를 이용할 수 있으면 좋겠다.

 궁금한 것이나 더 나은 코드 및 방법, 그리고 잘못된 것이 있다면 댓글에 남겨주시기 바란다.