[Java] 백준 12919번. A와B 2 (골드5)

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

 

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

12919번: A와 B 2

https://nodingco.tistory.com/30 의 시리즈 문제입니다.

 

1. 이해 (5분) - 1분

A와 B 문제와 언뜻 보면 똑같아보이는 문제입니다. 

하지만 조금 생각해보면 풀이를 위한 접근 방식이 전혀 다른걸 알 수 있습니다. 

앞의 문제에선 연산을 통한 결과가 맨 뒤 알파벳으로 나타나서 역순으로 따라가기만 하면 문제의 풀이가 가능하지만, 해당 문제에선 알파벳을 먼저 붙이고 뒤집기 때문에 맨 뒤 알파벳이 어떤 연산을 통해 나온 것인지 여러 경우가 생깁니다.

 

대신 문자열의 형태를 보고 어느정도 경우를 좁힐 수 있고 문자열의 길이도 앞 문제보다 훨씬 작습니다.

2. 계획 (5분) - 3분

재귀를 통해 뒷 문자열을 만들기 위해 가능한 경우를 역으로 되짚어갑니다.

대신 두가지 경우를 매 번 탐색하는게 아니라, 맨 뒷 문자가 A거나 맨 앞 문자가 B일때만 탐색합니다.

(1번 연산이 진행되면 문자열의 맨 뒤는 무조건 A, 2번 연산이 진행되면 맨 앞이 무조건 B)

 

그렇게 줄인 문자열의 길이가 앞의 문자열과 같아지면 두 문자열이 같은지, 즉 문제의 조건이 가능한지를 체크하고 그 결과를 저장합니다. 이때 True False에 따라 재귀문을 끝내는 조건을 움직여서 가능여부가 한 번 찾아지면 덮어씌워지지 않게했습니다.

3. 검증 (5분) - 1분

검증내용은 A와B 1번 문제와 유사하기때문에 패스하겠습니다.

4. 풀이 (30분) - 17분

재귀문 구현 부분은 조금 신경썼지만, 문자열을 조정하는 부분은 오히려 앞 문제보다 쉽게 구현 할 수 있었습니다.

5. 채점, 디버깅 

다행히 이번에도 한 번에 통과했습니다. 감사합니다!

 

 

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

public class Main {
	static int N;
	static char[] S;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		S = br.readLine().toCharArray();
		char[] T = br.readLine().toCharArray();

		N = S.length;

		makeS(T, T.length);

		if (N == 100) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}

	static void makeS(char[] T, int l) {
		if (l < N) {
			return;
		}
		if (l == N) {
			N = (checkS(T)) ? 100 : N;
			return;
		}

		if (T[l - 1] == 'A') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[i];
			}
			makeS(newT, l - 1);
		}

		if (T[0] == 'B') {
			char[] newT = new char[l - 1];
			for (int i = 0; i < l - 1; i++) {
				newT[i] = T[l - 1 - i];
			}
			makeS(newT, l - 1);
		}
	}

	static boolean checkS(char[] T) {
		for (int n = 0; n < N; n++) {
			if (T[n] != S[n]) {
				return false;
			}
		}
		return true;
	}
}