[BOJ] 11478 - 서로 다른 부분 문자열의 개수 (Java)

알고리즘

• 자료 구조
• 문자열
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

1. 문제

2. Idea

• 중복을 허용하지 않는 Set 인터페이스를 사용하여 HashSet으로 입력 정보를 저장한다.

3. 풀이

3.1. 변수 선언 및 HashSet 초기화

• 문자열 입력
• Set strs: 입력받은 문자열을 slicing하여 저장할 HashSet
  • Set 인터페이스는 중복을 허용하지 않기 때문에 "서로 다른 문자열"만을 저장할 수 있다.

String input=br.readLine();
Set<String> strs=new HashSet<>();

3.2. 문자열 자르기 및 HashSet에 add

• 이중 for문을 사용하여 문자열에서 나올 수 있는 문자열 조각을 모두 HashSet에 추가
• 중복 문자열이 추가되어도 상관 없음.(중복된 값은 추가되지 않기 때문에)

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

3.3. 결과 출력

• 결과 = HashSet의 크기

System.out.println(strs.size());

4. 전체코드

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