[백준/자바] 11478. 서로 다른 부분 문자열의 개수

문제

 

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

---

Algorithm

1. 처음엔 재귀를 이용해서 앞에서 부터 중복되는 문자열이 있으면 무시하는 방식으로 풀려 했는데 시간 초과 발생 (코드 짜는데 20분)

2. Set 이용해서 푸니까 바로 풀림 (코드 짜는데 1분)

3. 범위 보고 시간 복잡도 구하고 된다 싶으면 그냥 쉬운 개념 부터 쓰자...

 

---

 

 

Code

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

public class Main {
  static HashSet<String> hashSet = new HashSet<>();
  static int ans = 0;
  public static void main(String args[]) throws IOException { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String statement = br.readLine();
    substr(statement);
    System.out.println(hashSet.size());

  }

  public static void substr(String word) {
    // substring의 길이 표현
    for(int i=0;i<word.length();i++){
      // substr 재귀 돌리기
      for(int u=i+1;u<=word.length();u++){
        hashSet.add(word.substring(i,u));
      }
    }
  }

}