[백준/java] 12904. A와 B

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

🌱 문제

🌱 풀이

• 가능한 두가지 연산은 다음과 같다.

1. 문자열의 뒤에 A를 추가한다.
2. 문자열을 뒤집고 뒤에 B를 추가한다.

처음 시도한 방법

• 처음에 시도한 방법은 문자열 S에서 두가지 연산을 해보면서 문자열의 길이가 T의 길이와 같아질때까지 완전 탐색하는 것이었다.
• 코드는 다음과 같다.
  하지만 1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이 이기 때문에 최대 2^999번의 연산을 하게 되고, 시간초과는 당연한 결과 였다.

package week12.boj_12904;

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

//12904. A와 B
public class Somyeong {
	static String s,t;
	static int answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s=br.readLine();
		t=br.readLine();
		dfs(s);
		System.out.println(answer);
		
	}
	//
	public static void dfs(String s) {
//		System.out.println("s: "+s);
		if(s.length()==t.length()) {
			if(s.equals(t)) answer=1;
			return;
		}
		
		dfs(s+"A");
		
		StringBuffer sb = new StringBuffer(s);
		String reverseS=sb.reverse().toString();
		dfs(reverseS+"B");
	}
}

다시 시도한 방법

• 어떻게하면 수행시간을 줄이기 위해 완전탐색이 아닌 방법을 할 수 있을까를 고민하였다.

• 그래서 S에서 T로 가는 방식이 아니라 T에서 S로 가는 방식을 생각해 봤다. 이때는 연산도 반대로 해야하기 때문에 각각의 연산을 수행할 수 있는 조건이 정해져 있어서 수행시간을 줄일 수 있을 것 같았다.

• 먼저 연산을 거꾸로 하는 과정을 보자
  1. 문자열의 뒤에 A를 추가한다 -> (반대버전) 문자열 맨뒤 A를 제거한다.
2. 문자열을 뒤집고 뒤에 B를 추가한다 -> (반대버전) 문자열 맨뒤의 B를 제거하고 뒤집는다.

• 각각의 (반대방향) 연산을 하기 위해서는 다음과 같은 조건이 필요하이 있을때만 가능하다.

if(t.charAt(t.length()-1)=='A') // 문자열 t의 맨뒤가 A이면 제거 
			dfs(t.substring(0,t.length()-1));
if(t.charAt(t.length()-1)=='B') { // 문자열 t의 맨뒤가 B이면 제거하고 뒤집기 
			String newT=t.substring(0,t.length()-1);
			StringBuffer sb = new StringBuffer(newT); // String에는 바로 뒤집는 함수가 없어서 StirngBuffer의 함수를 이용하여 뒤집은 뒤 String으로 반환 
			String reverseNewT=sb.reverse().toString(); 
			dfs(reverseNewT);
}

• 조건을 만족할 때에만 다음 dfs 함수를 실행하게 되어서 통과과 되었다.
  하지만 시간복잡도가 구체적으로 어느정도가 되어서 채점이 통과한 것인지는 잘 모르겠다.

🌱 정답 코드

package week12.boj_12904;

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

//12904. A와 B
/*
 * 
 * 1. 문자열의 뒤에 A를 추가한다 -> (반대버전) 문자열 맨뒤 A를 제거한다. 
 * 2. 문자열을 뒤집고 뒤에 B를 추가한다 -> (반대버전) 문자열 맨뒤의 B를 제거하고 뒤집는다. 
 * 
 * 
 * 
 */
public class Somyeong {
	static String s,t;
	static int answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s=br.readLine();
		t=br.readLine();
		dfs(t);
		System.out.println(answer);
		
	}
	
	//t에서 s로 가는 방식 (DFS) 
	public static void dfs(String t) {
//		System.out.println("t: "+t);
		if(s.length()==t.length()) { // 문자열 t의 길이가 문자열 s의 길이와 같아지면 같은문자인지 확인하고 리턴 
			if(s.equals(t)) answer=1;
			return;
		}
		
		if(t.charAt(t.length()-1)=='A') // 문자열 t의 맨뒤가 A이면 제거 
			dfs(t.substring(0,t.length()-1));
		if(t.charAt(t.length()-1)=='B') { // 문자열 t의 맨뒤가 B이면 제거하고 뒤집기 
			String newT=t.substring(0,t.length()-1);
			StringBuffer sb = new StringBuffer(newT); // String에는 바로 뒤집는 함수가 없어서 StirngBuffer의 함수를 이용하여 뒤집은 뒤 String으로 반환 
			String reverseNewT=sb.reverse().toString(); 
			dfs(reverseNewT);
		}
	}
}