[백준] 12904 - A와 B (#파이썬 #투 포인터 풀이)

알고리즘 문제를 풀이한 후에 구글링 해보며 효과적인 풀이었는지 항상 확인한다.
"12904 파이썬" 키워드로 구글링 하면 대부분 reverse(), array slice를 사용한 풀이 밖에 없어서 풀이의 다양성을 추가하고자 투 포인터 풀이에 대해 작성한다.

Intuition

1. S를 T로 변환 가능? ➡️ T를 S로 변환 가능?

문제에서는 S를 T로 만들기 위해 '문자열의 뒤에 A를 추가'하거나 '문자열을 뒤집고 뒤에 B를 추가'할 수 있다고 한다. 이 두 방법을 이용해 S를 T로 만들 수 있는지 확인하면 된다.

문자열의 뒤에 A 혹은 B가 있을 때, A가 있다면 문자열에 곧바로 추가된 것이고 B가 있다면 뒤집혀서 추가되었다고 생각할 수 있다. 즉, 만들어진 결과를 보고 이전 상태를 생각할 수 있으므로 T를 S로 만들 수 있는지로 문제를 바꿔 생각할 수 있다.

2. 문자열에서 문자가 빠진 셈 치기, 문자열이 뒤집힌 셈 치기

T를 S로 변환할 때 문자열을 직접 조작할 경우 비효율적일 때가 많다. 그래서 문자열의 처음과 끝을 가리키는 포인터만 조작하여 마치 문자열이 조작된 것처럼 가정하도록 한다. 문자열에서 'A'를 빼는 게 아닌 빠진 셈 칠 수 있도록 포인터를 조작하고, 'B'를 빼는 게 아닌 빠진 셈 칠 수 있도록 포인터를 조작하고 뒤집어서 읽어야 함을 나타내는 상태 변수를 조작한다.

Approach

1. front 포인터와 back 포인터를 설정하고, 이 두 포인터 간 거리가 S의 길이와 같아질 때 조작을 멈춘다.
2. 뒤집어진 셈 쳐야한다면, front 포인터의 문자가 무엇인지 확인하고, 제대로 놓여 있다면, back 포인터의 문자가 무엇인지 확인해야 한다.
   1. 문자가 'A'이면 상대 포인터에 더 가깝게 조작한다.
   2. 문자가 'B'이면 상대 포인터에 더 가깝게 조작함과 함께 isFlipped 상태를 반전한다.
3. 조작을 멈췄을 때, 문자열이 '뒤집어져 있다 가정'해야 하는지, '제대로 놓여 있다고 가정'해야 하는지 알 수 있는 isFlipped 상태를 관리한다.

Complexity

Time Complexity

• O(|T|) : 최악의 경우 T의 모든 문자를 순회함

Space Complexity

• O(|T|): 입력 문자열 S와 T가 있으나 항상 S<T 임

Code

1. front 포인터와 back 포인터를 확인하며 뒤집혀야 하는지 확인함과 동시에 상대 포인터와 가까워진다.

S = input()
T = input()

len_s = len(S)
len_t = len(T)

back_ptr = len_t - 1
front_ptr = 0
isFlipped = False
while len_s != (back_ptr-front_ptr + 1):
    if not isFlipped:
        if T[back_ptr] != 'A':
            isFlipped = not isFlipped
        back_ptr -= 1
    else:
        if T[front_ptr] != 'A':
            isFlipped = not isFlipped
        front_ptr += 1

2. 조작을 멈췄을 때(=포인터 간 거리와 S 문자열의 길이가 같을 때) 포인터에서부터 문자를 읽으며 S와 같은지 확인한다.

isFind = False
if isFlipped:
    for k in range(len_s):
        if S[k] != T[back_ptr - k]:
            print(0)
            isFind = True
            break
    if not isFind:
        print(1)
else:
    for k in range(len_s):
        if S[k] != T[front_ptr + k]:
            print(0)
            isFind = True
            break
    if not isFind:
        print(1)

결과

• 한 번 오답이 발생했던 이유는 isFlipped 상태를 변경시켜줄 때 `not isFlipped` 가 아닌 `True`로 고정시켜 버렸기 때문이다. 초기값이 `False`이다 보니 `True`로 바꾸면 상태가 관리된다고 착각했다.