백준 11478: 서로 다른 부분 문자열의 개수(java)

문제

---

풀이

 

별도의 부분 문자열 생성 메소드를 작성하지 않고, String 클래스의 substring 메소드를 이용하였다.

시작 인덱스와 끝 인덱스를 입력하면 해당하는 범위의 부분 문자열을 반환하므로, 이중 for문을 이용해 인덱스를 구한다. beginIndex 이상, endIndex 미만의 범위임에 주의해야 한다.

for(int i=0; i<size; i++) {	//size=문자열 길이

	...
    
}

전체 문자열의 길이가 n일 때, 1부터 n의 길이를 가진 n종류의 부분 문자열을 생성할 수 있으므로 바깥쪽 for문은 n번 반복되도록 한다.

for(int i=0; i<size; i++) {
	for(int j=0; j<size-i; j++){
		String substring=str.substring(j, j+i+1);
        if(list.contains(substring))
		continue;
	else
		list.add(substring);
	}
}

길이가 i인 부분 문자열을 모두 구하려면 substring(0, i+1)부터 beginIndex와 endIndex를 1씩 증가시키며 반복해야 하므로 위와 같이 작성할 수 있다. 이때 서로 다른 부분 문자열만을 카운트해야 하므로 if-else문을 사용해 중복되지 않는 문자열만 컬렉션에 추가해 준다. 시간복잡도를 고려하여 list는 HashSet으로 선언한다(ArrayList 등을 이용하면 시간 초과).

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String str=br.readLine();
		int size=str.length();
		HashSet<String> list=new HashSet<>();
		
		for(int i=0; i<size; i++) {
			for(int j=0; j<size-i; j++){
				String substring=str.substring(j, j+i+1);
				if(list.contains(substring))
					continue;
				else
					list.add(substring);
			}
		}	
		System.out.println(list.size());
	}
}