오답노트 #9177 : 단어 섞기

풀이방법 및 문제점

2022.02.22

왠지 스택을 이용해 풀 수 있을 것 같아서 스택으로 구현해보았는데 틀렸다. 50%에서 실패가 뜬다.

얌전히 동적 프로그래밍 또는 그래프로 풀어야겠다.

 

내가 시도한 풀이법은 다음과 같다.

 

문자를 저장하는 스택 A, B, C를 선언한다.

첫 번째 단어를 스택 A에, 두 번째는 B에, 세 번째는 C에 앞 글자부터 push한다.

C의 top에 있는 글자가 A의 top에 있는 글자와 동일하다면 A와 C에서 한 글자를 pop한다.

C의 top에 있는 글자가 B의 top에 있는 글자와 동일하다면 B와 C에서 한 글자를 pop한다.

C의 top에 있는 글자가 A와 B 중 어느 것의 top과도 같지 않다면 no를 출력하고 다음 데이터로 넘어간다.

no로 판별하는 일 없이 C가 텅 빌 때까지 pop을 완료한다면 yes를 출력하고 다음 데이터로 넘어간다.

 

이 방법은 예제에 대해서는 올바른 답을 출력하였다.

그러나 백준 게시판에 있는 다음의 테스트케이스에 대하여 올바른 답을 출력하지 못했다.

1
a aba aaba
답: Data set 1: yes

이 테스트케이스를 찾은 게시글 링크

스택 C, 스택 A, 스택 B 모두의 top에 동일한 문자(이 테스트케이스에서는 'a')가 있는 경우에, A와 B 중 어느 쪽에서 pop을 해야 옳은지 결정하지 못하기 때문이다.

 

이 허점을 수정한다면 스택으로 문제를 풀 수도 있을 것 같다... 수정을 시도해봐야겠다. 성공하면 정답 게시글에 스택, 동적프로그래밍, 그래프 세 가지 해결법을 적는 것이고 실패하면 동적프로그래밍과 그래프로 푼 것만 적는 것이다...

 

코드

Java(2022.02.22)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	
	static String a, b, c;	//각 세트의 첫번째, 두번째, 세번째 문자열
	static Stack<Character> sa, sb, sc;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<n; i++) {
			//입력값 읽어오기
			String[] input = br.readLine().split(" ");
			a = input[0];
			b = input[1];
			c = input[2];
			
			//문자열들을 각각 스택에 넣기
			sa = new Stack<>();
			sb = new Stack<>();
			sc = new Stack<>();
			for(int j = 0; j<a.length(); j++)sa.push(a.charAt(j));
			for(int j = 0; j<b.length(); j++)sb.push(b.charAt(j));
			for(int j = 0; j<c.length(); j++)sc.push(c.charAt(j));
			
			//c 스택의 top에 있는 글자와 동일한 글자가 a 또는 b 스택의 top에 있다면 빼내고, 없으면 no 판별 후 루프 종료.
			int v = 1;
			while(!sc.isEmpty()) {
				char x = sc.peek();
				if(!sa.isEmpty() && x==sa.peek()) {
					sa.pop();
					sc.pop();
				}
				else if(!sb.isEmpty() && x==sb.peek()){
					sb.pop();
					sc.pop();
				}
				else {
					v = 0;
					break;
				}
			}
			
			//no 혹은 yes 출력.
			if(v == 0) System.out.println("Data set " + (i+1) + ": no");
			else System.out.println("Data set " + (i+1) + ": yes");
		}

	}
	

}