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

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

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

아주 직관적이며 쉬운 문제다. >> 부분 문자열 영어로 하면 substring..

자바에 substring()이라는 메소드가 있다 허허..

그걸 써서 어느 자료구조에다 넣느냐가 문제인데, 부분 문자열에 불가피하게 중복이 생기기 때문에

map 구조를 활용하여 중복을 다루는것이 가장 현명해보인다.

 

map을 생성해서 값을 put했다면 entry로 한바퀴 돌며 중복된값있나 체크하고 

있다면 그 값을 1로 replace()해준다면 바로 문제가 풀린다.

여기서 point는 substring(startidx,endidx);

 

다만 주의점은 substring(start,end)에서 부분문자열에서 startidx은 포함되지만 endidx는 포함되지 않는다.

예를들어 apple이라는 문자열이 있다고 가정할때, substring(0,1) 은 0 이상 1미만의 인덱스에 대한 부분 문자열을 return하기 때문에 a라는 값이 나온다. 

따라서, 아래 코드에서 이중 for문일때 j부분에서 (j<=len)을 해줘야한다.

또한 문자열의 최대 길이가 2000이라, 이중for문을 활용해도 무리가 없다는점까지 체크하자.

package 백준;
import java.util.*;
import java.io.*;
public class _11478_서로다른문자열의개수 {

	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);

	}

}