[알고리즘] 백준 12904번 문제

date

Nov 27, 2023

slug

al-11

author

status

Public

문제

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

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

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

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

예제 입력 1


B
ABBA

예제 출력 1

예제 입력 2


AB
ABB

예제 출력 2

풀이 코드


import sys
input = sys.stdin.readline

s=list(input().rstrip())
t=list(input().rstrip())

switch = False
while t:
    if t[-1]=='A':
        t.pop()
    elif t[-1]=='B':
        t.pop()
        t.reverse()
    if s == t:
        switch = True
        break
if switch:
    print(1)
else:
    print(0)

⭐ 핵심

S→T로 만들 수 있냐? = T→S로 줄일 수 있냐?

설명

문자열 S를 T로 바꾸는데 연산이 두가지인데, 이를 반대 관점에서 해석하여 문제를 풀 수 있다.

S→T

문자열의 뒤에서 A를 추가한다.

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

T→S

문자열의 뒤에서 A를 제거한다.

문자열의 뒤에서 B를 제거하고 문자열을 뒤집는다.

1번 관점에서 답을 구현하기 위해서는 문자열을 뒤집을지, 문자열의 끝에 추가할 것인지를 선택해야 한다.

이 선택은 연산 횟수를 증가시켜 시간 복잡도를 높이는 결과를 초래한다.

따라서 T를 S로 줄이는 과정을 문자열의 끝만을 확인하는 역연산(2번)을 통해 S를 T로 만들 수 있는지 없는지 알아낸다.

[알고리즘] 백준 12904번 문제 - A와B (그리디)

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이 코드

설명