[백준] 9177. 단어 섞기 (자바 JAVA)

[ 문제 ]  [백준] 9177. 단어 섞기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/9177

9177번: 단어 섞기

 

---

# 접근 방법 및 풀이 

 

• 어디 기업 코테 풀면서 봤던 문제 같아서 풀어봤다. 정답률 26으로 극악이다..
• 처음에 풀고 50프로만 맞아서 풀이방법 찾아봤다. bfs로 접근해서 다시 풀었다.
• 입력받은 3개의 단어들은 char[] 배열로 받고, 인덱스로 비교한다.
• Queue에는 첫번째 단어 인덱스와, 두번째 단어인덱스를 담기위해 Point로 선언.
• Point.x = 첫번째단어 인덱스, Point.y = 두번째 단어 인덱스다.
• bfs에서 방문체크는 visit[][] 2차원 배열로 선언하고, 행부분에는 첫번째단어, 열부분은 두번째 단어 인덱스를 체크한다.
• visit[][] = new visit[word1.length+1][word2.length+1]; 
• bfs에서 break 조건은 queue에서 pop한 첫번째단어 인덱스와 두번째단어 인덱스를 더했을 때 세번째 단어의 길이가 나온다면. 두 단어가 순서대로 잘 합쳐진 것이므로 ans = "yes"를 담고 break 한다.
• 자세한건 코드참조

# 주의할 점 

 

• visit[word1.length+1][word2.length+1] 크기 선언할 때 +1해줘야함. 

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj9177_단어섞기 {
	static char[] word1, word2, word3;
	static String ans = "";
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for(int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			word1 = st.nextToken().toCharArray();
			word2 = st.nextToken().toCharArray();
			word3 = st.nextToken().toCharArray();
			ans = "no";
			bfs();
			System.out.println("Data set " + tc + ": " + ans);
		}
	}

	private static void bfs() {
		Queue<Point> queue = new LinkedList<>();
		boolean visit[][] = new boolean[word1.length+1][word2.length+1];
		queue.add(new Point(0, 0));
		visit[0][0] = true;
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			int aIdx = p.x;
			int bIdx = p.y;
			if(aIdx + bIdx == word3.length) {
				ans = "yes";
				break;
			}
			if(aIdx < word1.length && word3[aIdx+bIdx] == word1[aIdx] && !visit[aIdx+1][bIdx]) {
				visit[aIdx+1][bIdx] = true;
				queue.add(new Point(aIdx+1, bIdx));
			}
			if(bIdx < word2.length && word3[aIdx+bIdx] == word2[bIdx] && !visit[aIdx][bIdx+1]) {
				visit[aIdx][bIdx+1] = true;
				queue.add(new Point(aIdx, bIdx+1));
			}
		}
	}
}

 

 

 

REVIEW

더 열심히 풀자..