[백준 / BOJ] 12904 A와 B

문제

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

12904번: A와 B

문자 'A'와 'B'가 주어진다. 

두 문자를 아래와 같은 규칙으로 연결해 문자열 T를 만든다.

1. 문자열 뒤에 A를 붙인다.

2. 문자열 을 뒤집고 뒤에 B를 붙인다.

이때, 문자열 S를 이용해 문자열 T를 만들 수 있는지 알아내는 프로그램을 만드는 문제다.

---

풀이

아이디어 문제다.

 

문자열 S를 이용해 문자열 T를 만들려면, 매 선택마다 2가지 경우의 수가 존재 하므로 총 2^N개의 경우의 수가 나온다. 

N이 최대 1000이므로, 위 와 같은 방법은 시간초과가 나온다.

 

이 문제는 문자열 S를 T로 만드는것이 아닌, 문자열 T를 역으로 문자열 S로 만드는식으로 하면 시간복잡도를 O(2^N)에서, O(N)으로 줄일 수 있는데, 이것을 생각해 내는것과 증명? 하는것이 어려웠다. 

 

T는 어떠한 문자열 A에 문자를 뒤로 연결해서 만든 문자열이다.

여기서 뒤로 라는 단어가 중요한데, S를 T로 만들경우, A를 붙이는경우, B를 붙이는경우 이렇게 2가지 선택지가 존재했다.

하지만, T는 이미 어떠한 문자를 뒤로 연결해 완성한 문자열이므로, 문자를 제거하는 선택지는 뒤에있는 문자를 제거하는 한가지 밖에없다.

 

따라서, 아래 과정을 거치고 완성된 문자열이 S와 같은지 비교만 해주면 된다.

1. 제거할 문자가 'A'라면, 그냥 제거한다.

2. 제거할 문자가 'B'라면, 제거하고 앞 뒤를 바꾼다.

 

주요 소스코드

	private int sToT(){
		int flip = 0;
		while(S.size() < T.size()){
			char c = '-';
			if(flip % 2 == 0) c = T.pollLast();
			else c = T.pollFirst();
			flip = (c == 'B') ? flip+1 : flip;
		}
		while(flip % 2 == 0 && !S.isEmpty() && S.peekLast() == T.peekLast()){
			S.pollLast();
			T.pollLast();
		}
		while(flip % 2 == 1 && !S.isEmpty() && S.peekLast() == T.peekFirst()){
			S.pollLast();
			T.pollFirst();
		}
		if(!S.isEmpty()) return 0;
		return 1;
	}

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/12904%20A%EC%99%80%20B/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃