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

 

간단한듯 어려운 문제였다. 하지만 한 메소드를 안다면 간단하게 해결할 수 있다.

 

우선 부분 문자열을 구하는 방법을 알아보자.

 

만약 abcde가 입력된다면 a b c d e ab bc cd de abc bcd cde abcd bcde abcde 이런식으로 나온다.

 

저 순서대로 출력하는 것은 반복문으로 처리하기에는 복잡하다.

 

반복문을 통해 해결하기에는 출력을 시작하는 자리가 지속적으로 변해 출력하기가 매우 까다롭다.

 

그렇다면 다른 규칙을 가지고 출력해보는 것을 생각해본다.

 

출력을 시작하는 자리를 고정해 본다.

 

a ab abc abcd abcde

b bc bcd bcde

c cd cde

d de

e

 

위와 같은 방식을 사용해도 모든 경우의 수가 나오는 것을 알 수 있다.

 

이제 조금 감이 잡히기 시작할 것이다. 

 

그렇다면 a ab abc abcd abcde처럼 여러 자리를 어떻게 출력할까?

 

그 때는 substring(i, j); 메소드를 이용하면 된다. 이는 String 변수의 i부터 j번째 앞까지 값을 출력한다.

 

만약 0, 1이 입력된다면 a,    0,2가 입력된다면, ab 이런식이다. 

 

그렇다면 위와 같이 출력하기 위해서는 i j가 

01 02 03 04 05

12 13 14 15

23 24 25

34 45

45

 

가 들어가면 해결된다.

 

코드로 확인하자.

 

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        int count = 0;

        for (String a : set) {
            count++;
        }

        System.out.print(count);

        br.close();

    }

}