문제 바로가기

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

문제 소개 및 재정의

참고할 문제: 백준. 12919. A와B 2

https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-12919-A%EC%99%80B-2-JAVA

문제 패턴

이전에 풀었던 A와B 2와 큰 맥락은 같다.
바뀐점은 입력값의 크기와 B를 추가하는 방법이다.
이번엔 B를 뒤에 추가하고 뒤집는게 아니고.
문자열을 뒤집고나서 뒤에 추가한다.
따라서 새로 추가되는 캐릭터는 항상 문자열의 맨끝에 위치한다.
따라서 복원과정에서 맨뒤의 캐릭터를 한번만 보면 결론까지 스트레이트하게 결정된다.
경우의 수가 1개라는 뜻이다.

어떻게 풀까? - 그리디

포인트

이전 코드에서 바뀐점 위주로.

메소드 bb()

<변경 전>
B가 맨 앞[0]에 있으므로 [1]~[L-1]까지를 카피해감

////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;
}

<변경 후>
B가 맨 뒤[L-1]에 있으므로 [0]~[L-2]까지를 카피해감

////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)-1-i];
	}
	return result;
}

메소드 recursion()의 재귀파트

<변경 전>
DFS 타고 갈거라 if를 따로 둬도 됨.

// 재귀 파트
char first = start[0];
char last = start[start.length-1];
if(last=='A') {
	recursion(aa(start));
} 
if(first=='B') {
	recursion(bb(start));
}

<변경 후>
last만 남기면 됨.
어라 생각해보니까 여기도 if 따로둬도 되네.
start를 공유하고 있는게 아니라서 상관없네.
그래도 안전하게 if - else if로 같은 분기점으로 묶음.

// 재귀 파트
char last = start[start.length-1];
if(last=='A') {
	recursion(aa(start));
} else if(last=='B') {
	recursion(bb(start));
}

코드

package solo.d1013;

import java.io.*;
import java.util.*;
public class BOJ_12904_A와B {
	// 입력고정
	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)-1-i];
		}
		return result;
	}
	//// 재귀
	static void recursion(char[] start) {
		// 바닥 조건
		if(start.length<=S.length) { 	// 여기서 끝내야 함.
			if(Arrays.equals(start, S)) { // 타겟이 되는 S와 바닥에서 만들어진 문자열이 같다면 전체 재귀 종료.
				answer = 1;				// 사실상 solve 대신 써도 됨.
				solve =true;			// 더 이상의 재귀적 확장을 막기 위함.
			}
			return;
		}
		
		// 문제 해결된 상태면 확장없이 종료. 앞으로 추가확장 안됨. 이미 Call된 것들만 남는데, 이것들도 똑같은 방식으로 종료됨.
		if(solve)
			return;
		
		// 재귀 파트
		char last = start[start.length-1];
		if(last=='A') {
			recursion(aa(start));
		} else if(last=='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);
		
	} // 메인종료
}

퍼포먼스

[ 12,784KB | 76ms ]

마무리

2와 거의 비슷한 문제이다. 대신 조금 더 쉬운것 같다.