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

---

이 문제는 문자열 S를 입력 받아, 서로 다른 부분 문자열의 개수를 구하는 프로그램을 만들어야 한다. 쉽게 말하면 abc를 입력 받았을 때 a, b, c, ab, ac, bc 이러한 집합의 개수를 구하는 문제이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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

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

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

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

1. 문자열을 입력 받는다.
2. 찾은 집합을 저장하고 전체 개수를 출력하기 위한 Set을 초기화한다.
3. 반복문을 실행시켜 각 부분 문자 집합을 구한다.
4. 하나 씩 만들어 set에 저장한다.
5. set의 길이를 리턴한다.

여기서 set은 중복이 허용되지 않기 때문에 자동적으로 중복된 부분 문자의 집합이 입력되면 삭제한다. 또한, 이 문제는 부분 집합을 리턴하는 것이 아닌 개수를 리턴하는 것이기 때문에 순서는 상관없다. 이런 점을 들어 set을 활용했고 일반적인 ArrayList 등과 달리 연산 처리가 빠르다는 장점이 있다.

마지막으로 substring() 함수는 인덱스를 기준, 합쳐줄 것 두 개를 전달받아 문자열의 문자를 하나씩 합치는 것이다. 쉽게 얘기하면 charAt() 을 사용해 문자를 하나 씩 뽑아 내어 합쳐 주는 것을 함수로 처리한다고 생각하면 좋다.

즉, i가 0인 경우 j는 1이기 때문에 “abc”가 입력 되었을 때 a와 b가 합쳐 진다.

---

이번 문제는 크게 생각해야할 것이 자료구조를 어떤 것을 사용할지와 문자를 어떻게 합쳐주어야할지 정도가 되겠다.

사실 실버3 레벨의 문제라고 명시되어 있긴 난이도가 크게 와닿지는 않았다.