[Python] BOJ(백준) 12904번 - A와 B

링크

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

난이도(solved.ac 참고)

골드5

풀이

나는 역으로 접근해서 B에서 A를 만들 수 있는지를 확인하였다. 두 가지 연산 모두 A 또는 B가 추가되는 연산이다. 따라서 역으로 생각하면 이것들을 하나씩 지워주면서 B의 길이를 줄여나가면 되는 것이었다.

 

BtoA라는 함수를 만들어서 b의 값을 이 함수를 적용시킨 값으로 해주었다.

마지막 값이 A라면 그 A값을 지운 새로운 new_b를 return하였고, 마지막 값이 B라면 b의 길이가 1보다 큰 때와 1일 때를 나눴다. 이유는 이렇게 나누지 않으면 계속 줄어들어서 결국 0이 되기 때문이다. b의 길이가 1보다 큰 경우라면 마지막 값을 없앤 값을 reverse하고 그것을 리스트로 바꿔준 뒤 다시 ''.join을 통해 문자열로 바꿔줬다.

 

예제를 예로 들어 설명해 보겠다.

ABBA -> ABB -> BA -> B(O)
ABB -> BA(X) -> B(X)

결과적으로 a와 b가 같을 경우에 1을 출력해야 하는데, b는 계속 한개씩 줄어든다. 따라서, b의 요소를 하나씩 줄여가는 과정에서 마침내 a와의 길이가 같아졌는데 값이 다르다면, 무조건 그 두개는 같아질 수 없다. 왜냐면 뒤집는 과정이라고 하더라도 결국 하나를 지워야 되기 때문이다. 그렇기 때문에 a의 길이와 b의 길이가 같지만 완벽하게 똑같은 경우가 아니라면 무조건 0을 출력해야 한다. 그게 아니라 a의 길이가 더 길다면, 더 볼 필요도 없다. b는 계속 감소하는데 a보다 길이가 짧다는 것은 결국 같아질 수가 없기 때문이다.