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

❓문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

---

❗출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다

---

시간초과

GPT에게 왜 시간초과인지 물어보았다

결론부터 말하면:
너가 짠 코드가 논리적으로는 맞지만,
List<Character>로 하나하나 문자를 관리하고
StringBuilder를 반복해서 만들고
Set<String> 에 계속 add하는 과정이
생각보다 시간이 오래 걸려서 백준에서는 시간 초과

1) String은 이미 내부적으로 char[] 배열을 갖고 있어. 그런데 너는 굳이 List<Character>로 변환했지? 이 과정이 필요 없는 메모리/시간 낭비

2) StringBuilder 만들기 비용
매 substring 만들 때마다 새로운 StringBuilder를 생성해서 매번 append하고 toString하는데, 이게 전체 조합 수 만큼 반복돼 → O(N²) 수준.

3) 부분 문자열 갯수 = O(N²)
단어 길이가 5000이라면, 부분 문자열 수는 약 (5000 * 5000) / 2 ≈ 12,500,000개.
이걸 다 StringBuilder + Set 삽입하면 시간 초과가 나.

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


class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String word = sc.next();
        
        List<Character> CharList = new ArrayList<>();
        Set<String> SetList = new HashSet<>();
        
        for (char c : word.toCharArray()) CharList.add(c); //단어끊기
        sc.close();

        
        for(int i=1; i<=CharList.size();i++){ //1개부터5개까지 (글자 개수)!!
            
            for(int k=0;k<=CharList.size()-i;k++){//시작점을 늘려나가
                StringBuilder sb = new StringBuilder();
                
                for(int j=k;j<k+i;j++){
                    sb.append(CharList.get(j));
                }
                SetList.add(sb.toString());
            }
        }
        System.out.print(SetList.size());
            
    }
}

---

문제 해결

🛠️ 해결 방법
List<Character> 버리고, 그냥 String 직접 사용.
substring 메서드로 바로 부분 문자열 만들기.
👉 String.substring()은 내부적으로 복사하지 않고 원본 문자열을 참조해서 동작하기 때문에 훨씬 빠름.

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

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String word = sc.next();
        sc.close();

        Set<String> set = new HashSet<>();

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

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