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

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

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

12904번: A와 B

 

1. 이해 (5분) - 2분

원리를 깨달으면 간단한 시뮬레이션 문제입니다.

다만, 문자열 관련해서 코드를 작성할 이해도가 필요할 것 같습니다.

문제는 간단명료합니다. 앞의 문자열에 두 가지 연산을 적용해서 뒤 문자열을 만들 수 있는지를 찾습니다.

간단히 생각하면 앞의 문자에 두가지 연산을 계속 적용해서 가능한 모든 경우의 수를 볼 수도 있겠지만... 

S의 길이가 1이고, T의 길이가 1000이라면? 2^1000가지 경우를 탐색해야 하니 어마어마한 일이겠죠. 

 

대신 연산의 조건을 파악하고 완성된 문자열에서 거꾸로 짚어가는 식으로 가부를 판단하려고 합니다.

2. 계획 (5분) - 4분

문자열에 적용한 연산 두가지는 모두 뒤쪽에 알파벳을 하나 더 붙입니다.

즉 최종결과에서 가장 뒤에 있는 알파벳은 이전에 적용된 연산이 무엇이었는지를 알려줍니다.

두 번째 문자열이 앞의 문자열보다 더 긴 길이만큼 연산을 거꾸로 적용하면 앞의 문자열과 같은 길이의 가능한 문자열이 나오게 되고 이 문자열을 앞의 문자열과 비교해서 가부를 판단할 수 있습니다.

 

문자열을 실제로 뒤집어서 풀이해도 되지만 저는 dir라는 boolean타입 변수를 하나 선언해서 투포인터 식으로 앞과 뒤에서 문자열을 줄여가는 방식으로 코드를 작성했습니다.

3. 검증 (5분) - 1분

시간복잡도나 메모리에서 문제가 생길 부분은 없을 것 같고, 구상한 대로 잘 풀이된다면 코드도 문제없이 작동할 겁니다.

4. 풀이 (30분) - 25분

문제의 이해와 계획은 금방 끝났지만 코드 작성에선 시간을 꽤 사용했습니다. 

반복문을 복잡하게 사용하다 보니 디버깅을 사용해서 제대로 동작하는지 검증을 철저히 했습니다.

5. 채점, 디버깅

다행히 제출은 한 번에 통과했습니다!

 

 

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

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

		char[] s1 = br.readLine().toCharArray();
		char[] s2 = br.readLine().toCharArray();

		int N = s2.length - s1.length;

		int front = 0, back = s2.length - 1;
		boolean dir = true;

		for (int n = 0; n < N; n++) {
			if (dir) {
				if (s2[back] == 'A') {
					back--;
				} else {
					back--;
					dir = false;
				}
			} else {
				if (s2[front] == 'A') {
					front++;
				} else {
					front++;
					dir = true;
				}
			}
		}

		boolean answer = true;

		if (dir) {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[front + n]) {
					answer = false;
					break;
				}
			}
		} else {
			for (int n = 0; n < s1.length; n++) {
				if (s1[n] != s2[back - n]) {
					answer = false;
					break;
				}
			}
		}

		if (answer) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}
}