백준 9177. 단어 섞기 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/9177

"조금더 빨리 돌아갈 수 있게 최적화를 시키자."

두 개의 문자열을 가지고 다른 문자열을 만들 수 있는지 없는지 확인하는 문제이다. 나는 DFS로 문제를 풀었다. 조건들이 문제를 굉장히 쉽게 만들 고 있었다.

- 순서를 지켜서 문자열을 조합해야 하고

- 모든 문자열을 사용해야 한다.

코딩을 다 하고 돌려보니 시간초과가 났다. 이상하다... 굉장히 심플해서 뭔가 더 성능을 높일만한 부분이 없는거 같은데 라고 생각하고, 이렇게 풀면 안되나?라고 생각했다. 

테스트 케이스를 만들어서 돌려보다가 문자열 A, B에 없는 문자가 C에 들어 있을 때, 재귀 횟수가 굉장히 높았다. 그래서 set을 이용하여 문자열의 포함 여부를 DFS 실행 전에 미리 체크해 주었더니, 시간초과 패스. 백준의 테스트 케이스에 따라 그냥 우연히 맞았는지, 이렇게 푸는게 맞는건지... 확신이 서질 않는다 ^^;;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N;
    static char[][] words;
    static char[] goal;
    static int aLen, bLen, cLen;
    static boolean find;
    static Queue<Integer> q = new LinkedList<>();
    static StringBuffer sb = new StringBuffer();
    static HashSet<Character> set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        int n =1 ;
        while(N-- >0) {
            words = new char[2][1];
            find = false;
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int i = 0; i < 2; i++) {
                words[i] = st.nextToken().toCharArray();
            }
            goal = st.nextToken().toCharArray();
            aLen = words[0].length;
            bLen = words[1].length;
            cLen = aLen + bLen;
            
            if(!check()) {
                sb.append("Data set "+ (n++) +": no\n");
                continue;
            }
            set.clear();
            solve(0,0,0);
            sb.append("Data set "+ (n++) +": "+ (find ? "yes":"no")+"\n");
        }
        System.out.print(sb.toString());
    }
    
    static void solve (int len, int aIdx, int bIdx ) {
        if(find) return ;
        
        if(len == cLen) {
            find = true;
            return ;
        }
        char target = goal[len];
        
        if(aIdx < aLen && words[0][aIdx] == target) solve(len+1, aIdx+1, bIdx);
        if(bIdx < bLen && words[1][bIdx] == target) solve(len+1, aIdx, bIdx+1);
    }
    
    static boolean check() {
        
        for (int i = 0; i < 2; i++) {
            int len = words[i].length;
            for (int j = 0; j < len; j++) {
                set.add(words[i][j]);
            }
        }
        
        for (int i = 0; i < goal.length; i++) {
            if(!set.contains(goal[i])) return false;
        }
        
        return true;
    }
}