[백준] 1972 놀라운 문자열 - 해시셋(HashSet) + DFS(깊이우선탐색) JAVA

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

코드설명

해시셋(HashSet) + DFS(깊이우선탐색) 를 활용합니다.

 

for문과 재귀문 두개 중 하나를 선택해서 할 수 있습니다.

 

for문을 활용할 경우 특이사항은, 각 0쌍, 1쌍, N-2쌍 의 기준으로 놀라운 문자열인지(유일한지) 판단하니, 밖의 for문으로 감싸고, 각 쌍으로 가능한 모든 경우를 만들기 위해 j = 0; j < N - i; j ++ 반복문을 돌립니다. 이떄 이 반복문의 제약조건이 j < N - i 인 이유는 j + i 가 더해졌을떄 >= N 이면 안되기에, j + i < N을 유지하기 위함입니다.그래야만 연결된 쌍이 IndexOutOfError가 안나겠지요.

for(int i=1; i<=N-2 + 1; i++) {
    HashSet<String> hashset = new HashSet<>();
    for(int j=0; j < N - i; j++) {

코드

for문을 사용한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static int Q;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str;
        while(true) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	str = st.nextToken();
        	if(str.equals("*")) break;
        	
        	if(func(str) == true) {
        		System.out.println(str + " is surprising.");
        	}else {
        		System.out.println(str + " is NOT surprising.");
        	}
        	
        }
    }
    
    private static boolean func(String str) {
    	boolean isAllUnique = true;
    	N = str.length();
    	for(int i=1; i<=N-2 + 1; i++) {
    		HashSet<String> hashset = new HashSet<>();
    		for(int j=0; j < N - i; j++) {
    			String newStr= ""; 
    			newStr += str.charAt(j);
    			newStr += str.charAt(j + i);
    			if(hashset.contains(newStr) == true) {
    				isAllUnique = false;
    				break;
    			}
    			hashset.add(newStr);
    		}
    		if(isAllUnique == false) return false;
    	}
    	
    	return isAllUnique;
    }
    
    
    
}

 

재귀문을 사용한 코드입니다.

package 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, M, C, T;
    private static int answer = 0;
    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine());
        
        
        while(true){
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	String str = st.nextToken();
        	if(str.equals("*")) break;
        	N = str.length();
        	
    		boolean isSurprising = true;
    		for(int diff=1;diff<=N-2 + 1; diff++) {
    			HashSet<String> hashset = new HashSet<>();
    			for(int num = 0; num < N; num++) {
        			if( func(0, num, diff, str, new String(""), hashset) == false) {
        				System.out.println(str + " is NOT surprising.");
        				isSurprising = false;
        				break;
        			}
    			}
    			if(isSurprising == false) break;
    		}
        	if(isSurprising == true) {	
        		System.out.println(str+" is surprising.");
        	}
        	
        }
    }
    
    private static boolean func(int level, int idx, int diff, String originalStr, String str, HashSet<String> hashset) {
    	if(level == 2) {
    		if(hashset.contains(str) == true) {
    			return false;
    		}
    		hashset.add(str);
    		return true;
    	}
    	if(idx >= originalStr.length()) return true;
    	
		boolean flag2 = func(level + 1, idx + diff, diff, originalStr, str + originalStr.charAt(idx), hashset);
    	return flag2;
    }
     
    
}