문제 (A와 B)
A와 B로만 이뤄진 문자열 s, t가 주어질 때,
두 가지 연산을 통해 s → t로 변환할 수 있을까?
가능하면 1, 아니면 0을 출력하라.두 가지 연산
1. 뒤에 A를 추가
2. 문자열을 뒤집고, 뒤에 B를 추가
조건
| Time limit | Memory limit |
|---|---|
| 2 sec | 512 MB |
- s의 길이 1~999
- T의 길이 2~1000
- s의 길이 < t의 길이
예제 
풀이
거꾸로 t→s로 만들어보자!
- deque에
t를 넣는다. - 현재 상태가 reversed인지 체크하기 위한 bool 변수
rev를 만든다. - 현재
que가 비어있지 않는 동안 다음 4-6 과정을 반복한다. rev값을 확인해서 현재 문자열이s와 같은지 확인한다.rev == True면서현재 문자열 == s라면True를 리턴한다.rev == False면서현재 문자열 == reversed(s)라면True를 리턴한다.
rev값을 확인해서 비교할 문자를 정한다.rev == True면 맨 앞 값을 pop한다. (popleft())rev == False면 맨 뒤 값을 pop한다. (pop())
- 확인한 문자가
B면rev를 뒤집어준다. - 만약 더 이상 확인할 que의 요소가 없다면 (즉, t를 전부 순회했다면) False를 리턴한다.
문제 (A와 B 2)
A와 B로만 이뤄진 문자열 s, t가 주어질 때,
두 가지 연산을 통해 s → t로 변환할 수 있을까?
가능하면 1, 아니면 0을 출력하라.두 가지 연산
1. 뒤에 A를 추가
2. 문자열을 뒤집고, 뒤에 B를 추가
조건
| Time limit | Memory limit |
|---|---|
| 2 sec | 512 MB |
- s의 길이 1~49
- T의 길이 2~50
- s의 길이 < t의 길이
예제 
풀이
거꾸로 t→s로 만들어보자!
- 문자열의 왼쪽은 B를 pop하고 오른쪽은 A를 pop해 값을 비교한다.
- 비교한 후의 문자열도 다시 que에 넣는다.
- deque에
t를 넣는다. 그리고que에 해당 deque를 넣는다. - 현재
que가 비어있지 않는 동안 다음 3-5 과정을 반복한다. que를 pop해서 deque를 얻어cur변수에 넣고 다음을 체크한다.cur가 비어있다면 다음으로 넘어가고cur의 문자열 == s면True를 리턴한다.
cur의 맨 앞 값이B라면 해당 값을 pop한 후que에 넣는다. (popleft())cur의 맨 뒤 값이A라면 해당 값을 pop한 후que에 넣는다. (pop())- 만약 더 이상 확인할 que의 요소가 없다면 False를 리턴한다.
⚠️ 4, 5번에서 주의할 점
- cur의 맨 앞 값이 B면서 맨 뒤 값이 A일 경우도 있다. (e.g. BXXXXA)
- python에서는 Call by assignment 방법을 따르기 때문에, deque와 같은 mutable 변수는 매개변수로 전해질 때 주소 값이 전해진다. 따라서 원래 cur을 그대로 넘기고 다시 값을 복구하면 무한 루프가 생성될 수도 있다.
→ cur를 pop하고 복구도 해야하면서, cur 자체를 매개변수로 넘기지 않아야 한다.
(또다른 방법으로는 dfs를 재귀적으로 사용하는 것도 가능할 것이다.)
(사실 시간 복잡도를 고려하지 않는다면, 굳이 pop을 하고 복구하고 복사하는 과정을 생략해도 될 것이다.)
코드
# BOJ 12904 A와 B
# A와 B로만 이뤄진 문자열;
# S를 T로 바꿀 수 있으면 1 없으면 0을 출력
# 가능한 2가지 연산: 뒤에 A추가 or 뒤집고 뒤에 B추가
# input
s = input() # 999
t = input() # 999
# solution
from collections import deque
class Solution:
def canChange(s, t):
rev = False
que = deque(t)
while que:
cur_str = "".join(que)
# rev 확인해서 값 비교 주의
if not rev and cur_str == s:
return True
elif rev and cur_str == s[::-1]:
return True
c = que.popleft() if rev else que.pop()
if c == 'B':
rev = not rev
return False
# output
ans = 1 if Solution.canChange(s, t) else 0
print(ans)# BOJ 12919 A와 B 2
# A와 B로만 이뤄진 문자열;
# S를 T로 바꿀 수 있으면 1 없으면 0을 출력
# 가능한 2가지 연산: 뒤에 A추가 or "뒤에 B추가 후 뒤집기"
# input
s = input() # 49
t = input() # 50
# solution
from collections import deque
import time
class Solution:
def canChange(s, t):
que = [deque(t)]
while que: # Lt - Ls # 50
cur = que.pop()
if not cur:
continue
if "".join(cur) == s:
return True
if cur[0] == 'B':
cur.popleft()
que.append(deque(reversed(cur))) # 50
cur.appendleft('B')
if cur[-1] == 'A':
cur.pop()
que.append(cur.copy()) # 50 # 주의 Call by assignment
cur.append('A') # X
return False
# output
ans = 1 if Solution.canChange(s, t) else 0
print(ans)- String
meraki