본문 바로가기
Algorithm(코딩테스트)/문자열

[백준 11478번 C++] 서로 다른 부분 문자열의 개수 (set/문자열)

by 카랑현석 2024. 2. 1.

문제

 

문제 분석

- 문자열의 size가 5라면, 문자열의 size가 1인 문자열, 2인 문자열, 3인 문자열, 4인 문자열, 5인 문자열을 모두 추출하고 중복을 제거하면 된다.

- 중복을 제거하여 저장하는 것은 set/map 자료구조를 활용하면 된다.

- 부분 문자열을 추출하기 위해서 substr을 사용하면 편하다.

- 최종적으로 set에 담겨있는 문자열의 개수를 출력하면 정답이다.

정답 코드

- string.substr(a,b) 는 a번째 인덱스의 문자부터 b의 길이만큼 반환하는 것이다.

ex)

s = "hyeons"; 

s.substr(3,2); 라고 하면 3번째 인덱스인 "o"부터 2개인 "on"을 추출한다.

//// str1 이 "Hello" 라면 str1.substr(3,2) 은 3번째 인자부터 2의 길이만큼 반환 -> lo 출력
#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;
unordered_set<string> us; // 중복 제거를 위해 set 사용

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	string s;
	cin >> s;
	for (int cnt = 1; cnt <= s.size(); cnt++) { // substr 시 start부터 cnt 개의 문자를 추출
		for (int start = 0; start <= s.size()-cnt; start++) { 
			us.insert(s.substr(start, cnt));
		}
	}
	cout << us.size();
	return 0;
}

 



교훈점

- 부분 문자열을 추출하기 위한 substr 함수에 대해 알게 되었다.

- 중복되는 부분을 제거하고 넣고 싶다면 set/map 자료구조를 사용하는 것이 효율적이다.