(22.06.09)(Baekjoon) 11478.서로 다른 부분 문자열의 개수

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

시간 제한 : 1초

메모리 제한 : 512MB

정답 비율 : 63.626%

 

문제

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

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

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

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

 

(※ 부분 문자열 : SubString) <== 기억하자.)

 

Java에서 SubString만 쓸 줄 알면 풀 수 있는 문제다.

반대로 SubString을 모르면 풀기 힘들어지는 문제다.

(필자는 SubString의 존재를 까먹어서 찾아보고 처음에 조합으로 풀려고 했다는건 비밀)

위 문제에서 부분 문자열은 뒤의 문자는 가져오지 않는다는 걸 유념하자.

주어진 문자열을 SubString으로 잘라가면서 모든 부분 문자열을 확인하면서, 각 문자별로 중복되지 않게 HashMap에 포함시키면서

마지막에 HashMap의 크기를 구하기만 하면 해결되는 문제다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {
	static String str;
	static String[] tgt;
	static int ans;
	static HashMap<String,Integer> map = new HashMap<String,Integer>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();
		for (int i = 0; i < str.length(); i++) {
			for (int j = i; j <= str.length(); j++) {
				if(i == j) continue;
				String sttr = str.substring(i,j); // subString : i번 문자열부터 j-1번 문자열까지 가져옴
				if(sttr.length() <= 1000) {
					map.put(sttr, 1); // HashMap에 sttr을 가지고 있는 값이 이미 있다면 알아서 안넣는다.
				}
			}
		}
		System.out.println(map.size());
	}

}