파이썬에서 주어진 제약 조건 하에 한 문자열을 다른 문자열로 변환할 수 있는지 확인하는 방법

문자 'A', 'B', '#' 세 종류만으로 구성된 두 문자열 s와 t가 주어져 있습니다. 우리는 아래의 연산 규칙을 적용하여 s를 t로 변환하는 것이 가능한지 확인해야 합니다.

연산 규칙

'A'는 왼쪽 방향으로만 이동할 수 있습니다.
'B'는 오른쪽 방향으로만 이동할 수 있습니다.
'A'와 'B'는 서로를 교차해 지나갈 수 없습니다.

예를 들어 입력이 s = "##AB##B", t = "A###B#B"라면 결과는 True입니다. s의 A는 가장 왼쪽 끝으로 쉽게 이동할 수 있고, 중간의 B는 한 칸만 오른쪽으로 옮기면 되기 때문입니다.

풀이 접근 방법

이 문제는 그리디 매칭 방식으로 해결할 수 있습니다. s의 각 문자를 순서대로 살펴보며 t에서 대응되는 위치를 찾고, 이동 방향 제약을 위반하는지 검사합니다. 구체적인 단계는 다음과 같습니다.

s와 t를 각각 문자 리스트로 변환합니다.
두 문자열의 길이가 다르면 False를 반환합니다.
s와 t에서 'A'의 개수 또는 'B'의 개수가 하나라도 다르면 False를 반환합니다.
i를 0부터 len(s) - 1까지 반복하며 다음을 수행합니다.
- s[i]가 '#'가 아니라면, j를 0부터 len(t) - 1까지 탐색합니다.
- t[j]가 s[i]와 다르면서 '#'도 아니라면 False를 반환합니다. 이는 'A'와 'B'가 서로 교차해야 하는 상황을 의미합니다.
- t[j]가 s[i]와 같다면 해당 위치를 '#'로 표시하고 다음 조건을 검사합니다.
  - s[i]가 'A'인데 i < j라면 False를 반환합니다. 'A'가 오른쪽으로 이동해야 하는 상황이기 때문입니다.
  - s[i]가 'B'인데 i > j라면 False를 반환합니다. 'B'가 왼쪽으로 이동해야 하는 상황이기 때문입니다.
- 매칭에 성공했으므로 내부 루프를 빠져나가 다음 문자를 처리합니다.
모든 검사를 통과하면 True를 반환합니다.

예제 코드

아래의 파이썬 구현을 통해 풀이 과정을 더 자세히 이해해 보겠습니다.

def solve(s, t):
    s = list(s)
    t = list(t)
    if len(s) != len(t):
        return False
    if s.count('A') != t.count('A') or s.count('B') != t.count('B'):
        return False
    for i in range(len(s)):
        if s[i] != '#':
            for j in range(len(t)):
                if (t[j] != s[i]) and t[j] != '#':
                    return False
                if t[j] == s[i]:
                    t[j] = '#'
                    if s[i] == 'A' and i < j:
                        return False
                    if s[i] == 'B' and i > j:
                        return False
                    break
    return True

s = "##AB##B"
t = "A###B#B"
print (solve(s, t))

입력

"##AB##B", "A###B#B"

출력

True

복잡도 분석

시간 복잡도는 O(n²)입니다. 외부 루프가 최대 n번 실행되고, 각 반복마다 내부 루프 역시 최대 n번 실행될 수 있기 때문입니다. 공간 복잡도는 문자열을 리스트로 변환하는 데 필요한 O(n)입니다.