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

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

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

---

문제

---

문제 풀이

부분 문자열을 만드는 핵심 알고리즘만 짜면 되는 문제다. C++의 경우에는 이중 for문으로 구현할 수 있고, 파이썬은 슬라이싱으로 구현할 수 있었다.

 

C++ 상세 풀이

for (int i = 0; i < str.length(); ++i) {
    tmp = "";
    for (int j = i; j < str.length(); ++j) {
        tmp += str[j];
        _set.insert(tmp);
    }
}

먼저 빈 문자열인 tmp를 만들고, 다음 for문에서 차례로 tmp에 문자열을 하나하나 추가한다.

 

이 문자열을 집합에 추가하면 되는데, 집합은 중복을 허용하지 않으므로 같은 문자열이 나와도 자동으로 걸러져 결국 집합의 크기가 부분 문자열의 크기가 된다.

예를 들어 ababc가 입력되었을 때,

1. i가 0일 때 : a, ab, aba, abab, ababc
2. i가 1일 때 : b, ba, bab, babc
3. i가 2일 때 : a, ab, abc
4. i가 3일 때 : b, bc
5. i가 4일 때 : c

가 차례대로 집합에 추가되는데 위에서 말한 것처럼 집합은 중복을 허용하지 않으므로 최종적으로 보라색 문자만 추가되며 서로 다른 부분 문자열만 남게 된다.

 

Python 상세 풀이

for i in range(len(text)):
    for j in range(i, len(text)):
        _set.add(text[i:j+1])

슬라이싱이라는 사기적인 방법이 있어 C++보다 훨씬 간단하게 구현된다.

 

큰 틀은 비슷한데, 입력받은 text에서 i부터 j까지의 문자열을 집합에 추가해주면 된다.

 

예를 들어 ababc가 입력되었을 때,

1. i가 0일 때 : a, ab, aba, abab, ababc
2. i가 1일 때 : b, ba, bab, babc
3. i가 2일 때 : a, ab, abc
4. i가 3일 때 : b, bc
5. i가 4일 때 : c

가 차례대로 집합에 추가된다. 그런데 집합은 중복을 허용하지 않으므로 최종적으로 보라색 문자만 추가되며 서로 다른 부분 문자열만 남게 된다.

 

코드 전문

C++

Python

 

소감

이전에 포스트했던 설명 중 잘못된 부분이 있어 다시 수정했다. 여기에 올린 예전 코드들도 틀린 코드가 좀 있는 것 같은데 걱정된다. 나중에 또 다시 풀어봐야겠다.