[BOJ] 12904번 A와 B (C++)

문제 (https://www.acmicpc.net/problem/12904)

12904번: A와 B

연산 1. 문자열의 뒤에 A를 추가한다.

연산 2. 문자열을 뒤집고 뒤에 B를 추가한다.

 

처음 시도 땐 S에서 두 가지 연산을 모두 진행시키며 T가 되는지 체크하는 방식으로 구현했는데 계속 메모리 초과가 발생했다. 

구현 방식을 바꾸어서 T를 보고 연산을 거꾸로 진행시켜서 S가 되는지 체크했다.

 

T의 가장 마지막 문자가 A일 때? 연산 1이 적용된 것이므로 추가된 문자인 A를 제거

T의 가장 마지막 문자가 B일 때? 연산 2가 적용된 것이므로 추가된 문자인 B를 제거 -> 뒤집힌 문자열을 다시 뒤집어줌

=> 두 경우 모두 마지막 문자를 제거하는 건 동일하므로 무조건 마지막 문자를 제거하고 B인 경우에만 체크해서 뒤집어 주었다.

 

연산을 거꾸로 적용한 T가 S와 일치한다면 1 출력하고 종료

T의 길이가 S의 길이와 같아질 때까지 일치하지 않는다면 S로 T를 만들 수 없는 것! 반복문을 탈출하고 0 출력

---

[소스코드]

---

2021-11-22

Gold 5

- 구현

- 문자열

- 그리디 알고리즘