[백준] 12919번: A와 B 2 파이썬

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

12919번: A와 B 2

망할 시간복잡도....

이 문제,, 처음엔 그냥 순서대로 다 해보면 될줄알았다..(브루트포스길래..)

그냥 s에서 A아니면 B추가 뒤집기 이거 다해서 문자열 일치하는지 검사하면 되겠다고 생각했다.

그렇게 단순하게 생각해서 처음에 쓴 코드.

def func(n):
  global check, s, t
  if(check == 1):
    return
  if(n == len(t)):
    if (s == t):
      check =1
    return
  else:
    s.append("A")
    func(n+1)
    s.pop()

    s.append("B")
    s.reverse()
    func(n+1)
    s.reverse()
    s.pop()

s = list(input())    
t = list(input())
check =0
func(len(s))
print(check)

돌아 가긴 하는데 시간초과...

너무 생각 없이 짜서 그런가..

 

질문게시판에서 s를 t로 만들지 말고 t에서 s를 만드는 게 낫다고 해서

다시 시도..

또 시간초과..

 

어째서? 

내 코드를 다시보니 난 s, t를 전역으로 선언해서 재귀함수 돌때마다 뒤집고 다시 뒤집은거 해제하고.. 두번씩 하게 되었던 것이다...

 

그래서 수정한 것이 이 코드

 

풀이

 

일단 s,t를 인자로 받아서 전 코드처럼 추가한거 빼고, 뒤집은거 되돌리고 .. 이런 부분을 없앴다.

그리고 reverse가 시간 복잡도가 O(n)이라 그래서 배열자체를 슬라이싱 하는것으로 시간복잡도를 줄였다!

아직 슬라이싱 ..어색해서 좀 더 익혀야할듯

def func(s, t):
  global check
  if(check == 1):
    return
  if(len(s) == len(t)):
    if (s == t):
      check =1
    return
  else:
    if(t[-1] == "A"):
      func(s, t[:-1])
    if(t[0] == "B"):
      func(s, t[:0:-1])



s = list(input())
t = list(input())
check =0
func(s, t)
print(check)

 

 

 

그리고 tmi

이 문제를 풀고 티어가 골드 3으로 올랐다 ~~ 야호

아직 허접하지만 더 열심히 하자앗

골드3 달성!