[백준/boj] 9177: 단어 섞기 / 브루트포스

문제

9177번: 단어 섞기

풀이

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static char[] word1, word2, word3;
	static int len1, len2, len3;
	static int N;
	static boolean answer;
	static String answerString;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		for (int t = 1; t <= N; t++) {
			st = new StringTokenizer(br.readLine());
			word1 = st.nextToken().toCharArray();
			word2 = st.nextToken().toCharArray();
			word3 = st.nextToken().toCharArray();
			len1 = word1.length;
			len2 = word2.length;
			len3 = len1 + len2;
			answer = false;

			Set<Character> set = new HashSet<>();
			for (int i = 0; i < Math.max(len1, len2); i++) {
				if(i < len1) set.add(word1[i]);
				if(i < len2) set.add(word2[i]);
			}
			boolean flag = true;
			for (int i = 0; i < len3; i++) {
				if (!set.contains(word3[i])) {
					flag = false;
					break;
				}
			}
			if (!flag) {
				bw.append("Data set " + t + ": no\n");
				continue;
			}

			func(0, 0, 0);

			answerString = answer ? "yes" : "no";
			bw.append("Data set " + t + ": " + answerString + "\n");
		}
		bw.flush();
		bw.close();
	}

	private static void func(int idx1, int idx2, int cnt) {
		if(answer) return; 
		
		if (idx1 + idx2 == len3) {
			answer = true;
			return;
		}

		if (idx1 < len1 && word3[cnt] == word1[idx1])
			func(idx1 + 1, idx2, cnt + 1);
		if (idx2 < len2 && word3[cnt] == word2[idx2])
			func(idx1, idx2 + 1, cnt + 1);
	}
}

 

1. set 에 word1 과 word2 를 중복 없이 담고, set에 word3 철자 중 하나라도 없는 경우에는 다음 Data set으로 넘어가게 해야 시간 초과가 나지 않는다.
2. func 함수에서는 word1, 2, 3의 앞부터 살펴본다. (func(0,0,0))

• word1 이 word3[cnt]와 같은 경우 자신의 인덱스(idx1)와 cnt 를 하나씩 증가시켜 (++로 하면 안됨) 재귀 호출한다.

word1이 함수를 호출하는 것은 word2랑은 일치하지 않지만 나랑은 일치해! 라는 뜻이다.
word2와 비교하기 전에 함수를 호출하기 때문이다.

• word2 도 동일하다.

이렇게 두가지 조건을 모두 훑어 보면 1만 일치한 경우, 2만 일치한 경우, 둘다 일치하지 않는 경우를 모두! 살펴보게 된다.

• idx1과 idx2 를 더해서 len3이 됐다는 것은 두 단어가 정상적으로 word3에 순서를 지키며 섞었다는 것을 의미한다.

> 이때 주의할 점은 word1 word2가 word3[cnt] 를 포함!하는 경우가 아니라 반드시 자신의 현재 인덱스와 비교를 해야한다는 점이다. 그 이유는 word1과 word2의 순서를 지키면서 섞어야하기 때문이다.

만약 word1,2 둘다 word3[cnt]와 자신의 현재 인덱스가 일치하지 않다는 것은 순서가 바뀌었거나,  a ab aaa 와 같이 특정 알파벳이 누락되고, 중복되는 알파벳이 추가되어 있는 경우라는 뜻이다.
이런 경우 idx1+ idx2 = idx3 를 만족하지 못할 것이므로 answer는 false가 된다.

• 이미 answer가 true면 다른 경우는 살펴보지 않고 return해도 되므로 if(answer) return; 을 꼭 ! 추가해줘야 시간 초과가 나지 않는다.