백준 11478번: 서로 다른 부분 문자열의 개수
주어진 문자열 S에서 만들 수 있는 모든 '부분 문자열(substring)' 중에서, 서로 다른 것이 총 몇 개인지 세는 문제입니다. HashSet을 이용하여 중복을 효율적으로 제거하는 방법과, 이중 for 반복문으로 모든 부분 문자열을 생성하는 로직을 묻는 문제입니다.
✅ 문제 개요
| 항목 | 내용 |
|---|---|
| 문제 번호 | 11478번 - 서로 다른 부분 문자열의 개수 |
| 난이도 | 실버 3 |
| 핵심 알고리즘 | 자료구조, 문자열, 해시를 사용한 집합과 맵 |
✅ 문제 설명 요약
- 입력: 첫째 줄에 문자열 S가 주어집니다. (S의 길이는 1,000 이하, 알파벳 소문자로만 구성)
- 출력: S의 서로 다른 부분 문자열의 개수를 출력합니다.
- 규칙:
- 부분 문자열은 연속된 일부분을 의미합니다. 예를 들어 "abac"의 부분 문자열에는 "a", "b", "c", "ab", "ba", "ac", "aba", "bac", "abac" 등이 있습니다.
- "a"처럼 중복되는 부분 문자열은 한 번만 세야 합니다.
✅ 풀이 전략
이 문제는 두 가지 핵심 과제로 나눌 수 있습니다: 1) 모든 부분 문자열을 생성하기와 2) 생성된 부분 문자열들의 중복을 제거하기입니다.
1️⃣ 핵심 아이디어: HashSet으로 중복 자동 제거
- "서로 다른" 개수를 세어야 하는 문제에서는,
HashSet을 사용하는 것이 가장 효과적입니다. Set자료구조는 원소의 중복을 허용하지 않으므로, 우리가 모든 부분 문자열을 생성하여Set에 넣기만 하면 중복은 알아서 처리됩니다.- 최종적으로
Set의 크기(size())를 구하면 그것이 바로 정답이 됩니다.
2️⃣ 모든 부분 문자열 생성하기: 이중 for문
- 문자열 S의 모든 부분 문자열을 생성하려면, 시작 위치와 끝 위치를 지정해주어야 합니다.
- 이중
for반복문을 사용하여 모든 (시작, 끝) 조합을 만들 수 있습니다.- 바깥쪽
for문 (변수i): 부분 문자열의 시작 인덱스를 0부터S.length() - 1까지 순회합니다. - 안쪽
for문 (변수j): 부분 문자열의 끝 인덱스 다음 위치를i + 1부터S.length()까지 순회합니다.
- 바깥쪽
- Java의
String.substring(i, j)메소드는i번째 인덱스부터j-1번째 인덱스까지의 부분 문자열을 반환합니다.
String S = "abac";
HashSet<String> set = new HashSet<>();
for (int i = 0; i < S.length(); i++) {
for (int j = i + 1; j <= S.length(); j++) {
set.add(S.substring(i, j));
}
}3️⃣ 알고리즘 설계
HashSet<String>을 생성하여 부분 문자열을 저장합니다.- 입력 문자열
S를 받습니다. - 바깥쪽
for문을i = 0부터S.length()까지 반복합니다. - 안쪽
for문을j = i + 1부터S.length() + 1까지 반복합니다. S.substring(i, j)를 이용해 부분 문자열을 추출하고HashSet에 추가(add)합니다.- 모든 반복이 끝나면,
HashSet의 크기(set.size())를 출력합니다.
예시: abac
1. i=0:
- j=1: "a" 추가
- j=2: "ab" 추가
- j=3: "aba" 추가
- j=4: "abac" 추가
2. i=1:
- j=2: "b" 추가
- j=3: "ba" 추가
- j=4: "bac" 추가
3. i=2:
- j=3: "a" 추가 (이미 있으므로 무시됨)
- j=4: "ac" 추가
4. i=3:
- j=4: "c" 추가
5. 최종 Set: {"a", "ab", "aba", "abac", "b", "ba", "bac", "ac", "c"}
6. Set의 크기는 9.
✅ Java 코드 예제
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.HashSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String S = br.readLine();
// 1. HashSet 생성
HashSet<String> subStrings = new HashSet<>();
// 2. 이중 for문으로 모든 부분 문자열 생성 및 Set에 추가
for (int i = 0; i < S.length(); i++) {
for (int j = i + 1; j <= S.length(); j++) {
subStrings.add(S.substring(i, j));
}
}
// 3. Set의 크기(서로 다른 부분 문자열의 개수) 출력
bw.write(String.valueOf(subStrings.size()));
bw.flush();
bw.close();
br.close();
}
}⚠️ 실전 주의사항
| 항목 | 설명 |
|---|---|
substring 범위 | S.substring(begin, end)는 begin 인덱스부터 end-1 인덱스까지 추출합니다. end 인덱스는 포함되지 않는다는 점에 유의해야 합니다. |
| 시간 복잡도 | 이중 for문이 O(N²), substring 연산이 평균 O(N), HashSet의 add가 평균 O(1)이므로, 총 시간 복잡도는 약 O(N³)에 가깝습니다. S의 길이가 1000이므로 최대 약 10⁹ 연산으로 시간 초과가 날 수 있지만, substring과 HashSet의 해시 계산이 실제로는 더 효율적으로 동작하여 통과 가능합니다. |
HashSet의 원리 | HashSet은 내부적으로 각 문자열의 해시코드(hash code)를 계산하여 중복 여부를 빠르게 판단합니다. 이 덕분에 수많은 부분 문자열을 효율적으로 관리할 수 있습니다. |
| 메모리 | 최악의 경우, 길이가 N인 문자열의 부분 문자열 개수는 N*(N+1)/2개입니다. N=1000일 때 약 50만 개의 문자열이 HashSet에 저장될 수 있으므로 메모리 사용량을 고려해야 합니다. |
📝 마무리 요약
✔️ "서로 다른" 개수를 세는 문제는 HashSet을 사용하면 중복을 자동으로 처리할 수 있어 매우 편리합니다.
✔️ 문자열의 모든 부분 문자열을 생성하려면 시작점과 끝점을 지정하는 이중 for 반복문을 사용합니다.
✔️ String.substring(i, j) 메소드를 활용하여 i부터 j-1까지의 부분 문자열을 추출합니다.
✔️ 생성된 모든 부분 문자열을 HashSet에 추가한 뒤, 최종적으로 Set의 크기를 출력하면 정답입니다.
