백준 11478 <서로 다른 문자열의 개수>

11478번: 서로 다른 부분 문자열의 개수 (acmicpc.net)

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

 

부분 문자열의 갯수를 출력하는 문제이다. 

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

 

즉 어떠한 문자열의 부분문자열들은 서로 겹치는게 분명히 존재하겠다.

겹치지 않는 부분문자열의 가짓수.

 

일단 겹치지 않는 조건중에 가장 잘 보이는건 글자의 갯수겠다. 

사실 부분문자열을 영어로 해석하면 substring이다. 하지만 이 부분문자열이라는 함수는 자바에서 이미 구현을 해놓았다. 

따라서 그 메소드를 활용하면 될거같다는 생각을 일단 했고.

 

두번째, 최대범위를 보면 1000이다. 뭐 n^2까지 시간을 써도 되겠다는 생각이 든다.

 

이중 for문을 돌며, substring의 모든 가짓수를 맵에다가 넣는게 일단 첫번째 생각일것같다.

만약 겹치는 부분 문자열이 있다면 이 맵의 벨류는 1보다 큰 값이 나올 것이고,

이때는 필터링을해서 count를 해서 답을 내면 쉽게 풀 수 있을것같다.

 

counting을 할때 map을 사용했으니 map을 관찰하기 좋은 entry type을 사용한다면 답이 쉽게 나올 수 있다. 

 

substring() 만 잘 쓰면 쉽게 푸는 문제.

 

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		HashMap<String,Integer> hs = new HashMap<String,Integer>();
		int len = str.length();
		
		for(int i=0 ; i<len; i++) {
			for(int j=i+1; j<=len; j++){
				if(hs.containsKey(str.substring(i,j))) {
					hs.put(str.substring(i,j), hs.get(str.substring(i, j))+1);
				}
				else {
					hs.put(str.substring(i,j), 1);
					
				}
			}
		}
		
		for(Map.Entry<String,Integer> entry : hs.entrySet()) {
			if(entry.getValue() > 1) {
				hs.replace(entry.getKey(), 1);
			}
		}
		int ans = 0;
		for(Map.Entry<String,Integer> entry : hs.entrySet()) {
			ans += entry.getValue();
		}
		System.out.println(ans);

	}

}