BOJ 11478 - 서로 다른 부분 문자열의 개수

문제

문자열 S가 주어졌을 때, 서로 다른 부분 문자열(연속된 일부분)의 개수를 구하라.

입력

첫째 줄에 알파벳 소문자로 이루어진 문자열 S가 주어진다 (길이 1 이상 1,000 이하).

출력

서로 다른 부분 문자열의 개수를 출력한다.

예제

입력	출력
`ababc`	`12`

풀이

모든 부분 문자열을 HashSet에 넣어 중복을 제거한 후 크기를 출력한다.

길이 1부터 S.length()까지 이중 반복한다
각 길이 i에 대해 시작 인덱스를 이동하며 substring을 추출한다
추출한 부분 문자열을 HashSet에 삽입하여 중복을 자동 제거한다
최종 HashSet의 크기가 정답이다

핵심 아이디어: 문자열 길이가 최대 1,000이므로 부분 문자열은 최대 약 500,500개이고, HashSet으로 충분히 처리 가능하다.

코드

package ASP_study.day299;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
 
public class Day263BOJ11478서로다른부분문자열 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String S = br.readLine();
		HashSet<String> hs = new HashSet<>();
 
		for (int i = 1; i <= S.length(); i++) {
			int length = i;
			while (length <= S.length()) {
				hs.add(S.substring(length - i, length));
				length++;
			}
		}
 
		System.out.println(hs.size());
	}
}

복잡도

시간: O(N^3) - 이중 반복 O(N^2) * substring 생성 O(N)
공간: O(N^3) - HashSet에 저장되는 부분 문자열 총 길이

문제