[P&B] #96 BAEKJOON 11478

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

문제 설명

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

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

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

 

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

 

출력

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

 

나의 문제 풀이 코드

import java.util.*;
import java.io.*;
public class bj11478 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        HashSet<String> result = new HashSet<>();
        for (int i = 0; i < str.length(); i++) {
            for (int j = i+1; j < str.length()+1; j++) {
                result.add(str.substring(i,j));
            }
        }
        System.out.println(result.size());
    }
}

 

문제 풀이 코멘트

문제 설명을 보고 처음에는 한자리로 이루어진 부분 문자열, 두 자리로 이루어진 부분 문자열... 이런식으로 저장하여 구해야 하나라는 생각을 했습니다. 하지만 코드를 구현하다보니 첫 번째 자리 문자로 시작하는 부분 문자열, 두 번째 자리 문자로 시작하는 부분 문자열...로 부분 문자열들을 구해 저장하면 되겠다는 생각이 들었습니다. 실제로 그렇게 구현하는 것이 훨씬 쉬웠습니다.

다만 한가지 주의할 점은  String substring(int beginIndex, int endIndex)은 beginIndex 위치에서 시작하여 endIndex의 이전 index까지의 값을 리턴한다는 의미이기 때문에 endIndex의 값을 잘 설정해 주는 것이 중요했습니다.