백준 11478 서로 다른 부분 문자열의 개수 (JAVA)

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

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

 

백준 11656번 문제와 유사한 문제지만

부분 문자열을 저장할 자료구조를 잘 선택하지 않으면 시간 초과로 오답이 나오는 문제입니다.

ArrayList를 이용할 경우 시간 초과가 발생하여 HashSet을 이용해야 한다는 점만 유의하면 될 것 같습니다.

 

import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();
 
        HashSet<String> list = new HashSet<>();
 
        for (int i = 0; i <= s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (!list.contains(s.substring(i, j))) {
                    list.add(s.substring(i, j));
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        sb.append(list.size()+"\n");
        System.out.println(sb);
 
    }
}
 

 

HashSet(상단)과 ArrayList(하단) 차이