[BOJ] 12919번: A와 B 2

 

(( 한 번 다시 봐도 좋을 문제 ))

 

문제 링크

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

 

 

 

TIL

• 반대로 생각해보는 연습하기 (거꾸로)
  • 문제에서 S에 1) 끝에 A를 추가하거나 2) 끝에 B를 추가한뒤 배열 뒤집기를 요구했으니
  • 반대로 T에서 1) 끝에서 A를 제거하거나 2) 배열을 뒤집고 B를 제거하는 것을 해볼 수 있음 !! 
  • 다만 전체 배열로 비교하는 것은 까다롭고, 비효율적이니 T의 마지막 문자를 기준으로 확인하는 게 좋음 
• 재귀에서는 연속된 return 처리 필수 
• 모든 경우의 수를 봐야하는 경우에는 꼭 이렇게 재귀형식으로 해야함
  • 처음 코드의 경우, 모든 경우의 수를 볼 수 없음 >> 틀린 이유

 

[ 처음 코드] - TC는 모두 돌아가나, 정답 제출 실패

import copy

S = list(input())
T = list(input())

for i in range(len(T)):
    if S == T:
        print(1); exit()

    next_A = copy.deepcopy(S); next_B = copy.deepcopy(S)
    next_A.append('A')
    next_B.append('B'); next_B = next_B[::-1]
    if next_A == T[:len(S)+1]:
        S.append('A')
    elif next_B == T[:len(S)+1]:
        S.append('B')
        S = S[::-1]
    else:
        print(0); exit()

• 좋은 코드라고 생각되지 않음 
  • 불필요한 메모리 사용이 너무 많고, 시간 측면에서도 효율적인거 같진 않음

 

 

Code

[ 내 코드 ]

S = list(input())
T = list(input())
# 재귀를 사용하지 않으면 모든 경우의 수를 확인할 수가 없어서 틀리게 됨
# T가 BA이고, S가 A인 경우, A를 제거하고 B만 남은 경우만 고려하게 될 수 있음
# 가지치기가 포함된 완전 탐색 필요 ~ 뭐 일종의 백트래킹
def compare_last(t):
    if len(t)==0:
        return 0

    if t == S:
        return 1

    if t[-1] == 'A':
        ret = compare_last(t[:-1])
        if ret == 1:
            return 1

    if t[0] == 'B':
        t = t[::-1]
        ret = compare_last(t[:-1])
        if ret == 1:
            return 1

print(1) if compare_last(T)==1 else print(0)

• 재귀이기때문에 연속된 Return을 처리하지 않으면 틀림 !! 
• 재귀의 형태나 매개변수는 자유롭게 설정 가능

 

 

[ 다른 사람 코드 참고용 ]

def canTransform(t, s):
    if t == s:
        return True
    if len(t) < len(s):
        return False

    result = False

    if t[-1] == 'A':
        result |= canTransform(t[:-1], s)
    if t[0] == 'B':
        result |= canTransform(t[1:][::-1], s)

    return result

S = input()
T = input()

print(1 if canTransform(T, S) else 0)

• 나처럼 Return해서 표현할 수도  있지만 위 코드처럼 T/F로 두고, or 연산 처리 가능 !! 
  • 기억해두기

 

s = input()
t = input()

answer = 0
def sub(str1, target):
  global answer
  if len(str1) == len(target):
    if target == str1:
      answer = 1
    return
  if target[-1] == 'A':
    sub(str1, target[:-1])
  if target[0] == 'B':
    #target = target
    sub(str1, target[:0:-1])

sub(s, t)
print(answer)

• 리스트로 받지 않고도 이렇게 표현 가능