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

문제 링크

---

1. 문제 풀이

문자열 $S$ 의 서로 다른 부분 문자열의 개수를 구하는 문제로 중복을 제거할 수 있는 집합 자료구조와 부분 문자열을 생성할 수 있는 함수나 메서드를 활용하면 간단하게 해결할 수 있다.

---

2. 코드

1. 해시를 사용한 집합과 맵 [Java]

substring 메서드로 시작 인덱스와 끝 인덱스를 넣어서 부분 문자열을 생성했다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Set<String> set = new HashSet<>();
        String str = br.readLine();

        for (int i = 0; i < str.length(); i++) {
            for (int j = i; j < str.length(); j++) {
                set.add(str.substring(i, j + 1));
            }
        }

        System.out.println(set.size());
    }
}

2. 해시를 사용한 집합과 맵 [C++]

substr 함수로 시작 인덱스와 길이를 넣어서 부분 문자열을 생성했다.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    unordered_set<string> st;
    for (int i = 0; i < s.size(); i++) {
        for (int j = 1; j <= (int)s.size() - i; j++) {
            st.insert(s.substr(i, j));
        }
    }

    cout << st.size();
}

---

3. 풀이 정보

1. 해시를 사용한 집합과 맵 [Java]

언어	시간	메모리	코드 길이
Java 11	692 ms	226968 KB	511 B

2. 해시를 사용한 집합과 맵 [C++]

언어	시간	메모리	코드 길이
C++ 17	540 ms	209732 KB	352 B

---