[백준] 11478 서로 다른 부분 문자열의 개수 - 문자열 + HashSet JAVA

https://www.acmicpc.net/problem/11478

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

코드설명

문자열과 HashSet 을 활용한 문제입니다.

 

문제 로직입니다.

1. 1부터 주어진 문자열의 길이만큼 반복문을 돕니다.

2. 1번의 반복문 안에서 size가 매개변수로 전달되고, substring으로 차례차례 각 size만큼 범위를 넘어가지 않게 String을 구합니다.

3. 중복처리를 위해 HashSet에 넣습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static String str = "";
	public static Character[] answerStr;
	public static HashSet<String> hashset = new HashSet<String>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str = st.nextToken();
    	
    	for(int i=1;i<=str.length();i++) {
    		simulate(i);
    	}
    	System.out.println(hashset.size());
    }
	
	public static void simulate(int size) {
		for(int i=0; i<str.length();i++) {
			
			if( i + size > str.length()) return ;
			String s = str.substring(i, i+size);
			hashset.add(s);
			
		}
	}
	
}

 

만약 Main 함수에서 반복문을 사용하지않고, 함수에서 모든 처리를 다 진행하게 한 코드입니다.

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

public class Main {
    private static int N, T, K, M;
    private static int answer = 0;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		String S = st.nextToken();

		HashSet<String> hashset = new HashSet<>();
		dfs(-1, S, new String(""), hashset);
		System.out.println(hashset.size() - 1);
	}
    
    public static void dfs(int idx, String S, String str, HashSet<String> hashset) {
    	if(hashset.contains(str) == false) {
    		hashset.add(str);
    	}
    	
    	if(idx == -1) {
    		for(int i=0; i<S.length();i++) {
    			dfs(i, S, str, hashset);
    		}
    	}
    	else if(idx < S.length()){
    		dfs(idx + 1, S, str + S.charAt(idx), hashset);
    	}
    	
    }
    
    
}

 

이번에는 함수에서 개수를 반환하도록 합니다.

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

public class Main {
    private static int N, T, K, M;
    private static int answer = 0;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		String S = st.nextToken();

		HashSet<String> hashset = new HashSet<>();
		System.out.println(dfs(-1, S, new String(""), new HashSet<String>() ) - 1);
	}
    
    public static int dfs(int idx, String S, String str, HashSet<String> hashset) {
    	if(hashset.contains(str) == false) {
    		hashset.add(str);
    	}
    	
    	if(idx == S.length()) {
    		return hashset.size();
    	}
    	
    	int ret = 0;
    	if(idx == -1) {
    		for(int i=0; i<S.length();i++) {
    			ret = Math.max(ret, dfs(i, S, str, hashset));
    		}
    	}
    	else if(idx < S.length()){
    		ret = Math.max(ret, dfs(idx + 1, S, str + S.charAt(idx), hashset));
    	}
    	
    	return ret;
    }
    
    
}