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

문제

---

문제링크: https://www.noj.am/11478

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

 

 

문제 분석

---

 

문제를 읽어보면 문자열의 부분 문자열들을 파악하는게 전부인 문제다.

부분 문자열이 뭐냐하면

 

<출처: https://youtu.be/Pssocd3sTEc>

 

"연개소문"을 예로 들면

"개", "소", "개소문" 등이 부분 문자열이다.

🐶🐮

 

오케이, 부분 문자열도 뭔지 알았으니까

이제 그거 카운트만 해주면 되겠네.

 

그럼 그걸 위해서는 뭐가 필요할까?

 

필요한 것 목록.

1. 문자열에서 부분 문자열로 분리.

2. 중복된 요소들을 걸러 담아줄 수 있는 자료구조.

아마 C언어로 풀었다면, char형 문자들을 하나하나 받아 부분 문자열들을 완성시켰을 거다.

 

하지만 내가 요즘 쓰는 언어는 C++
무려 라이브러리라는 것이 존재하는 갓갓언어다.

C에서 C++로 넘어오니 즁말 행복하다

 

아무튼, 그 도구들이 라이브러리에 다 준비되어있다는 것 아니겠나

간단하게 코드 앞부분에 #include <bits/stdc++.h> 한번 박아주자

이 헤더가 싫으면 <string>이랑 <set> 쓰면 된다.

 

부분 문자열을 추출해주는 substr()함수와

중복을 없애주는 자료구조 set이 오늘의 주인공이다.

(무려 정렬까지 해줌)

 

substr()을 잘 모른다면 이 링크(psychoria의 블로그)를 참고.
set을 잘 모른다면 이 링크(Anthropology의 블로그)를 참고.

 

자세한 풀이

---

 

벌써 위에서 감 다 잡았겠지만

그래도 핵심부분은 자세히 설명을 해보겠다.

 

우선 문자열의 처음부터 끝까지 인덱스 하나하나 보자.

int l = S.length();
for(i = 0; i < l; i++) {

i=0부터 문자열 길이만큼 반복문을 돌려주고

 

현재 인덱스(i)의 위치부터 문자열 끝까지 문자를 하나씩 늘려가며 set에 넣어주는 거다.

부분 문자열 뽑아내는 걸 substr()로 날먹가능

for(int i = 0; i < l; i++)
	for(int j = i; j < l; j++)
		M.insert(S.substr(i, j - i + 1)); // j-i+1을 하면 현재(i)부터 끝(l)까지의 길이가 된다.

 

예를 들어 conan을 입력받았다고 하면 0부터 4까지 돌아갈 것이다.

i == 0일 때: c, co, con, cona, conan
i == 1일 때: o, on, ona, onan
i == 2일 때, n, na, nan
i == 3일 때, a, an
i == 4일 때, n

마지막 n은 i가 2일 때, 이미 들어갔으므로 i가 4일 때 나오는 n은 set에 추가되지 않는다.
그럼 최종적으로 몇 개?
=> 14개!

 

이렇게 입력받은 문자열의 길이만큼 반복문을 돌면서,

substr()으로 set에 넣어주면 끝!

 

중복되는 요소는 set이 자동으로 걸러주니까 편-안

 

와우 너무 간단하쥬?

 

코드 (C++)

---

#include <bits/stdc++.h>
using namespace std;

set<string> M; // set 자료구조.
string S; // 입력받을 문자열.

int main(){	
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> S;
	
	int i,j,l=S.length(); // 반복문 내에서 매번 length()를 수행하는 것보다 한 번만 담아주자.
	
	for(i=0;i<l;i++) // 0번째 인덱스부터 끝까지 반복.
		for(j=i;j<l;j++) // 현재(i)인덱스부터 끝까지 반복.
			M.insert(S.substr(i,j-i+1)); // j-i+1을 하면 현재(i)부터 끝(l)까지의 길이가 된다.
	
	cout << M.size(); // 마지막에 set에 담겨있는 요소의 개수를 출력하면 완성~
}

 

주석을 봐도 잘 이해가 안 되면, 댓글로 물어보세요