JAVA 백준 11478 서로 다른 부분 문자열의 개수 (집합과 맵)

 

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

 

---

문제

1. 첫째 줄에 문자열 S ( 1 <= S.length() <= 1000 ) 가 입력된다.
2. 문자열 S의 서로 다른 부분 문자열 (1 <= 부분 문자열 <= S.length() )의 개수를 구하여 출력하라.

---

 

 

정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String S = br.readLine();

        Set<String> set = new HashSet<>();

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

        System.out.println(set.size());
    }
}

 

 

간단하게 중복이 허용되지 않는 자료 구조인 Set을 이용하였다.

 

모든 부분 문자열을 Set에 추가하면 Set이 중복을 모두 제거하여 중복되지 않은 것들만 남겨주기 때문에 Set의 크기를 출력하면 중복되지 않은 서로 다른 부분 문자열의 개수가 출력된다.