[Greedy] 12940번 A와 B

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

알고리즘

• Greedy

풀이

포인트

• 문자열 S를 T로 만들기 위해서는 다양한 경로를 따져야 하지만, T에서 S를 만드는 경로는 하나라는 점.

Greedy

이 문제를 처음 접했을 때, 가장 먼저 떠오른 풀이는 bfs이었다. 즉, 현재 상태에서 두 가지 선택권이 있고, 각 상태를 만들기 위한 최소 연산 수를 기록하며 bfs를 한다면, 문자열 T를 만들 수 있는지 여부를 구할 수 있다고 생각했다. 전형적인 bfs 문제라고 생각하고 아래와 같이 코드를 짰다.

[Source Code]

from collections import deque

def func_1(x):
    return x+'A'
def func_2(x):
    return x[::-1]+'B'

s = input()
t = input()
visited = {}
q = deque()
funcs = [func_1,func_2]
visited[s] = 0
q.append(s)
while q:
    s = q.popleft()
    if len(s) > len(t):
        continue
    for func in funcs:
        ns = func(s)
        if visited.get(ns) == None:
            visited[ns] = visited[s] + 1
            q.append(ns)
if visited.get(t) == None:
    print(0)
else:
    print(1)

근데 메모리 초과가 뜨는 것이다! 메모리 초과가 날만한 부분이, visited 딕셔너리 뿐인데...

최악의 경우를 생각해보자. S의 길이가 1이고 T의 길이가 1000이라고 생각해보자. S를 T로 만들기까지 총 999개의 문자열을 붙여야한다. 하나의 문자열을 추가할 때마다, 두 가지 선택권이 주어진다. 이는 곧, $2^{999}$개의 문자가 visited배열에 담길 수 있다는 의미 아닐까? 그러면 메모리 초과가 나는 것은 당연하다. 사실, 메모리가 무한정이라고 가정해도 시간초과가 뜰게 뻔하다. 결국 시간 복잡도가 $O(2^{999})$이기 때문이다.

따라서 이 문제는 다른 접근법이 필요하고, 그리디하게 생각함으로써 해결할 수 있었다.

문제에서는 S를 T로 만들 수 있는지 여부를 조사하라고 했지만, 만약 S를 T로 만들 수 있다면, 역으로 T를 S로 만들 수 있을 수 있다. 그리고 이렇게 거꾸로 생각해보면, S > T의 경로를 따라갈 때와는 다르게, 한 가지 경로만 따라가면 된다.

아래와 같이 생각해보자.

• 현재 문자열의 마지막 문자열이 A인 경우
  • 문자열의 뒤에 A를 추가한 경우에 한해, 해당 문자열이 만들어질 수밖에 없다.
  • 따라서 A를 지워줌으로써 이전 상태로 복원한다.
• 현재 문자열의 마지막 문자열이 B인 경우
  • 문자열을 뒤집고 뒤에 B를 추가한 경우에 한해, 해당 문자열이 만들어질 수밖에 없다.
  • 따라서 B를 지워주고, 다시 문자열을 뒤집어서 이전 상태로 복원한다.

위의 과정을 반복하다가, 현재 상태의 문자열이 S의 길이보다 작아지면, 만들어질 수 없는 경우이므로 0을 출력한다.

아래 소스코드의 시간 복잡도는 $O(10^2)$이다.

[Source Code]

s = input()
t = input()
while s != t:
    if t[-1] == 'A':
        t = t[:-1]
    else:
        t = t[:-1][::-1]
    if len(s) > len(t):
        print(0)
        exit()
print(1)