문제 바로가기

https://www.acmicpc.net/problem/12919

문제 소개 및 재정의

문자열 S와 T가 주어진다.
두 문자열은 'A', 'B'로만 이루어져있다.
문자열을 바꾸는 방법은 두가지가 있다.
뒤에 A를 추가하는것.
뒤에 B를 추가하고 거꾸로 뒤집는것.
.
이때, S가 바뀌는 작업을 거듭해서 T가 될수 있는지 여부를 구하시오.
.
S의 길이 1~49
T의 길이 2~50

문제 패턴

패턴을 잘 모르겠다.
일단 문자열이 사용된다는 것.
따라서, char[]을 쓰든 해싱작업을 거쳐야 메모리 퍼포먼스가 나올것이다.
.
최적해를 구하는 방식도 아닌것 같다. DP는 아닌것 같다.
그래프 문제도 아닌것 같다.
완전탐색을 시도해보자.

어떻게 풀까? - 완전탐색

포인트

S에서 T로 가는 모든 경우의 수를 만드는 방식으로 접근했다.
최악의 경우 S의 길이는 1, T의 길이는 50이다.
이때 49번의 문자열 확장과정이 필요하다.
한번의 확장과정에서 2 가지의 경우의수가 나온다.
따라서 249 가지의 경우의 수가 나온다.
이는 1015 와 맞먹는 수치로 퍼포먼스가 안 나온다.
알면서도 방법이 없어서 해봤다.
역시나 시간초과가 발생했다.

T에서 S로 가는 방법을 택했다.
해체는 조립의 역순이다.
조립하는 경우의 수와 해체하는 경우의 수가 다를 때가 있는것 같다.
이 문제가 그러하다.
조립할때는 항상 2가지 경우의 수가 나오지만,
해체할때는 문자열의 맨앞과 맨뒤의 캐릭터에 따라서 경우의 수가 바뀐다.
쉽게 말해서, 맨앞이 B일때만 B를 추가하는 확장이 가능했던거고.
맨 뒤가 A일때만 A를 추가하는 확장이 가능했던거다.
앞과 뒤를 경우의 수에 맞게 나눠보았다.
.
AA => 뒤의 A삭제 가능
AB => 아무것도 못함. 바닥 조건임
BA => 앞의 B삭제 가능, 뒤의 A삭제 가능
BB => 앞의 B삭제 가능
.
T에서 S로 가는 경우 0,1,2가지의 경우의 수가 나올수 있기 때문에
일종의 가지치기 효과를 기대했다.

T를 S로 만드는 작업을 복원이라고 하자.
그렇다면 S를 T로 만드는 작업의 순서를 반대로 하면된다.
A를 추가하는 로직을 복원화해서 메소드로 만들었다.
B를 추가하는 로직을 복원화해서 메소드로 만들었다.
이후에는 재귀적으로 DFS 과정을 통해서 문자열을 복원했고.
목표 문자열과 동일한 길이가 됐을때, 같은 문자열인지 확인했다.
.
같은 문자열인게 확인되면, 더 이상의 재귀작업(확장)을 하지 않도록
막는 로직도 추가했다.

코드

package study.week13;

import java.io.*;
import java.util.*;
public class BOJ_12919_A와B2_2 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	// 세팅
	static char[] S;
	static char[] T;
	static int target;
	static int answer;
	static boolean solve;
	// 메소드

	//// A를 제거한 결과를 반환
	static char[] aa(char[] start) {
		int l = start.length;
		char[] result = new char[l-1];
		for (int i = 0; i < l-1; i++) {
			result[i] = start[i];
		}
		return result;
	}
	////B를 제거한 결과를 반환
	static char[] bb(char[] start) {
		int l = start.length;
		char[] result = new char[l-1];
		for (int i = 0; i < l-1; i++) {
			result[i] = start[(l-1)-i];
		}
		return result;
	}
	//// 재귀
	static void recursion(char[] start) {
//		System.out.println(Arrays.toString(start)); // 디버깅용 코드
		// 바닥 조건
		if(start.length<=S.length) { 	// 여기서 끝내야 함.
			if(Arrays.equals(start, S)) { // 타겟이 되는 S와 바닥에서 만들어진 문자열이 같다면 전체 재귀 종료.
				answer = 1;				// 사실상 solve 대신 써도 됨.
				solve =true;			// 더 이상의 재귀적 확장을 막기 위함.
			}
			return;
		}
		
		// 문제 해결된 상태면 확장없이 종료. 앞으로 추가확장 안됨. 이미 Call된 것들만 남는데, 이것들도 똑같은 방식으로 종료됨.
		if(solve)
			return;
		
		// 재귀 파트
		char first = start[0];
		char last = start[start.length-1];
		if(first=='A' && last=='A') {
			recursion(aa(start));
		} 
		else if(first=='A' && last=='B') {
				return;
		} else if(first=='B' && last=='A') {
			recursion(aa(start));
			recursion(bb(start));
		} else if(first=='B' && last=='B') {
			recursion(bb(start));
		}
		return;
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		S = input.readLine().toCharArray();
		T = input.readLine().toCharArray();
		target = S.length;
		// 세팅
		// 작업
		recursion(T);
		// 출력
		System.out.println(answer);
		
	} // 메인종료

}

퍼포먼스

[ 11,540KB | 64ms ]

참고 후 리팩토링

package study.week13;

import java.io.*;
import java.util.*;
public class BOJ_12919_A와B2_3 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	// 세팅
	static char[] S;
	static char[] T;
	static int answer;
	static boolean solve;
	// 메소드

	//// A를 제거한 결과를 반환
	static char[] aa(char[] start) {
		int l = start.length;
		char[] result = new char[l-1];
		for (int i = 0; i < l-1; i++) {
			result[i] = start[i];
		}
		return result;
	}
	////B를 제거한 결과를 반환
	static char[] bb(char[] start) {
		int l = start.length;
		char[] result = new char[l-1];
		for (int i = 0; i < l-1; i++) {
			result[i] = start[(l-1)-i];
		}
		return result;
	}
	//// 재귀
	static void recursion(char[] start) {
//		System.out.println(Arrays.toString(start)); // 디버깅용 코드
		// 바닥 조건
		if(start.length<=S.length) { 	// 여기서 끝내야 함.
			if(Arrays.equals(start, S)) { // 타겟이 되는 S와 바닥에서 만들어진 문자열이 같다면 전체 재귀 종료.
				answer = 1;				// 사실상 solve 대신 써도 됨.
				solve =true;			// 더 이상의 재귀적 확장을 막기 위함.
			}
			return;
		}
		
		// 문제 해결된 상태면 확장없이 종료. 앞으로 추가확장 안됨. 이미 Call된 것들만 남는데, 이것들도 똑같은 방식으로 종료됨.
		if(solve)
			return;
		
		// 재귀 파트
		char first = start[0];
		char last = start[start.length-1];
		if(last=='A') {
			recursion(aa(start));
		} 
		if(first=='B') {
			recursion(bb(start));
		}
		return;
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		S = input.readLine().toCharArray();
		T = input.readLine().toCharArray();
		// 세팅
		// 작업
		recursion(T);
		// 출력
		System.out.println(answer);
		
	} // 메인종료

}

맨뒤가 A일때 걸고
맨앞이 B일때 걸고
if문을 따로 쓰면 else if문을 주렁주렁 쓰지 않아도 된다는것을 깨달았다. (맞힌 사람의 코드를 보고)

마무리

두가지 스킬이 중요했다.
1. 확인되면 모든 재귀를 멈추는 방법. 이제 슬슬 익숙해짐.
2. 정방향 탐색과 역방향 탐색의 경우의 수가 다를수있다.
이 사실에 익숙해지고, 바로 떠올려서 기본적으로 고려할수 있을만큼 연습하자.