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

문제 해석

• 문자열 S를 입력받아 문자열로 만들 수 있는 모든 부분문자열의 개수를 구하면 된다.
• 예를 들면, ababc가 주어졌다는 가정하에 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 존재하는데, 같은 것을 제거하면 a, b, c, ab, ba, bc, aba, bab, abc, abab, babc, ababc로 12개가 된다.
• 단, 부분문자열은 연속된 일부분만 가능하며, 길이는 1보다 같거나 커야한다.

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String S = br.readLine(); //문자열
        br.close();

        HashSet<String> partS = new HashSet<String>(); //부분 문자열 중복 없이 넣기

        for(int i = 0; i < S.length(); i++) { //문자열의 크기로 쪼개서 각각의 자리 문자를 넣는다
            for(int j = i+1; j <= S.length(); j++){ //연속된 숫자이므로 i+1부터 시작해야한다. 다음 문자열부터 시각해야하니까
                partS.add(S.substring(i, j));
                /*
                    예를 들면, S가 abca이라고 가정하고
                    i = 0
                    j = 1 ~ 3까지 반복

                        j = 1
                        처음에는 S.subString(0, 1)이니까 0 인덱스부터 1 인덱스전까지의 문자열을 넣는다.
                        => a

                        i = 0
                        j = 2
                        S.subString(0, 2)이니까 0 인덱스부터 2 인덱스전까지의 문자열을 넣는다.
                        => ab
                   이런식으로 반복하여 구한다.
                 */
            }
        }
        
        //이미 중복을 제거했으니 partS의 사이즈를 출력하면 된다.
        bw.write(partS.size() + "");
        bw.flush();
        bw.close();
    }
}

• 코드에 대한 설명은 주석으로 작성해두었다.

결과

느낀 점

• 시간이 많이 소요된다. => 항상 보안해야하는 문제...
• 이번 문제는 subString() 함수가 다 한 문제 같다.