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

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

문제

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

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

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

접근

이중 반복을 도는데 첫 반복문은 1부터 문자열의 길이까지 돈다. 이는 부분문자열의 길이를 말한다. 즉, 길이가 5인 문자열에 대해 길이가 1부터 5길이 까지 잘라주기 위함이다.
안쪽 반복문에선 문자열의 0번 인덱스부터 돌며 앞선 반복문이 현재 가리키는 길이까지 substring으로 잘라 저장한다.
모두 갈이별로 자르며 Set에 저장하며, 새로운 부분문자열이 나올 때마다 set에 있는 중복된 문자열인지 확인한다. 아니면 개수를 누적한다.

문제해결

> 입력받을 문자열을 S에 입력받고 substring으로 자를 문자열을 str에 저장한다.
> 자른 부분문자열의 중복 방지를 위해 부분문자열의 집합을 Set인 s로 선언한다.
> 이중 반복문으로 바깥은 문자열의 길이, 안쪽은 입력받은 문자열의 인덱스를 나타낸다.
> substring으로 S문자열을 j번부터 j+i번까지 잘라 저장한다.
> set안에 해당 문자열이 있지 않으면 cnt를 누적하고 다음 부분문자열들을 위해 set에 저장한다.

코드

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

public class Main {
    //11478번 서로 다른 부분 문자열의 개수
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        Set<String> s = new HashSet<>();
        String S = br.readLine();
        String str;
        int cnt = 0;
        for(int i = 1; i <= S.length(); i++) {
            for(int j = 0; j < S.length(); j++) {
                if(j + i > S.length()) break;
                str = S.substring(j, j+i);
                if(!s.contains(str)) {
                    s.add(str);
                    cnt++;
                }
            }
        }
        System.out.print(cnt);
    }
}

후기

substring을 처음 써보는 계기가 됐다.
3중 반복을 쓰기 싫어 탐색하다 알게 되었다.