백준 ABB to BA (Hard) [32293] 파이썬(Python) 코드 + 해설

백준 32293 문제 ABB to BA

문제 설명

'A'와 'B'로만 구성된 문자열 S가 주어진다. 다음 동작을 더 이상 수행할 수 없을 때까지 반복한다:

1. 문자열 S에서 첫 번째로 등장하는 부분 문자열 "ABB"를 찾는다.
2. 그 위치를 i라고 할 때, 𝑆𝑖와 𝑆𝑖+1를 각각 'B'와 'A'로 바꾸고, 𝑆𝑖+2​를 문자열에서 제거한다.
   • 즉, "ABB"를 "BA"로 변환한다.
3. 문자열에 "ABB"가 더 이상 존재하지 않을 때까지 이 과정을 반복한다.

반복이 끝난 후의 문자열 S를 출력하는 프로그램을 작성해야 한다.

 

문제 해결 방법

이 문제는 문자열에서 특정 패턴("ABB")을 찾아 변환하는 작업을 반복적으로 수행해야 한다. 그러나 문자열의 길이가 최대 5×10^5이므로 단순한 탐색으로는 시간 초과가 발생한다.

효율적인 해결을 위해 다음과 같은 방법을 사용한다

1. 연결 리스트를 이용한 시뮬레이션

• 문자열의 각 문자를 노드로 갖는 연결 리스트를 만든다.
• 각 노드는 이전 노드와 다음 노드에 대한 포인터를 가진다.
• 이렇게 하면 문자 삭제와 삽입이 O(1)시간에 가능하다.

2. 패턴 발생 위치 추적

• 문자열을 처음부터 탐색하여 'A'인 위치를 큐에 저장한다.
• 각 위치에서 'ABB' 패턴이 형성되는지 확인한다.
• 변환이 발생하면 인접한 위치에서 새로운 'ABB' 패턴이 생길 수 있으므로, 해당 위치들을 큐에 추가한다.

3. 알고리즘 단계

1. 초기화
   • 문자열을 문자 리스트로 변환하고, 각 문자에 대해 이전 노드와 다음 노드를 저장한다.
   • 각 위치에 대해 이전 노드(prev), 다음 노드(next)를 저장하는 배열을 만든다.
   • 'A'인 위치를 모두 큐에 넣는다.
2. 변환 반복
   • 큐에서 위치를 하나씩 꺼내어 처리한다.
   • 해당 위치에서 'ABB' 패턴이 있는지 확인한다.
     • 𝑆 𝑖 = ′ 𝐴 ′,  𝑆 𝑛 𝑒 𝑥 𝑡 𝑖 = ′𝐵 ′ 인 경우
   • 패턴이 있으면 변환을 수행한다:
     • 𝑆 𝑖 를 ′𝐵 ′ 로, 𝑆 𝑛 𝑒 𝑥 𝑡 𝑖  를 ′ 𝐴 ′ 로 변경
     •  𝑆 𝑛 𝑒 𝑥 𝑡 𝑛 𝑒 𝑥 𝑡 𝑖 를 삭제하고 연결 리스트를 업데이트
   • 변환으로 인해 영향을 받을 수 있는 인접한 위치들을 큐에 추가한다.
3. 결과 생성
   • 변환이 모두 끝나면 연결 리스트를 순회하여 최종 문자열을 생성한다.

백준 ABB to BA (Hard) 32293 파이썬(Python) 정답 코드

import sys

def main():
    import sys
    input = sys.stdin.readline

    t = int(input())
    MAX_N = 5 * 10**5 + 5

    for _ in range(t):
        n = int(input())
        S = input().strip()
        chars = list(S)
        n = len(chars)

        # 노드의 이전 위치와 다음 위치를 저장하는 배열
        prev = [-1] * n
        next = [-1] * n
        for i in range(n):
            if i > 0:
                prev[i] = i - 1
            if i < n - 1:
                next[i] = i + 1

        # 'A'인 위치를 큐에 저장
        from collections import deque
        queue = deque()
        in_queue = [False] * n
        for i in range(n):
            if chars[i] == 'A':
                queue.append(i)
                in_queue[i] = True

        while queue:
            i = queue.popleft()
            in_queue[i] = False

            # 현재 위치에서 'ABB' 패턴 확인
            if chars[i] != 'A':
                continue
            if next[i] == -1 or next[next[i]] == -1:
                continue
            j = next[i]
            k = next[j]
            if chars[j] == 'B' and chars[k] == 'B':
                # 변환 수행
                chars[i] = 'B'
                chars[j] = 'A'

                # 노드 k 삭제
                next[j] = next[k]
                if next[k] != -1:
                    prev[next[k]] = j

                # 변환으로 인해 영향을 받을 수 있는 위치들을 큐에 추가
                for idx in [prev[prev[i]] if prev[i] != -1 else -1, prev[i], i, j, next[j]]:
                    if idx != -1 and chars[idx] == 'A' and not in_queue[idx]:
                        queue.append(idx)
                        in_queue[idx] = True

        # 결과 문자열 생성
        result = []
        idx = 0
        while prev[idx] != -1:
            idx = prev[idx]
        while idx != -1:
            result.append(chars[idx])
            idx = next[idx]

        print(''.join(result))

if __name__ == "__main__":
    main()

 

 

백준 32293 ABB to BA (Hard) 파이썬 코드 설명

1. 데이터 구조 초기화

• chars: 문자열의 각 문자를 리스트로 저장한다.
• prev, next: 각 위치에서 이전 위치와 다음 위치를 저장하는 배열을 생성한다.
  • 초기화 시, prev[i] = i - 1, next[i] = i + 1로 설정한다.
  • 문자열의 처음과 끝에서는 prev[0] = -1, next[n - 1] = -1로 설정한다.

2. 큐 초기화

• 문자열을 처음부터 탐색하여 문자 'A'인 위치를 모두 큐에 넣는다.
• in_queue 배열을 사용하여 중복 추가를 방지한다.

3. 변환 반복

• 큐에서 위치를 하나씩 꺼내어 처리한다.
• 현재 위치 i에서 다음을 확인한다:
  • chars[i] == 'A'인지 확인한다.
  • next[i]와 next[next[i]]가 존재하는지 확인한다.
  • chars[next[i]] == 'B'이고 chars[next[next[i]]] == 'B'인지 확인한다.
• 조건이 모두 만족하면 변환을 수행한다:
  • chars[i] = 'B'
  • chars[next[i]] = 'A'
  • 노드 next[next[i]]를 삭제하고 연결 리스트를 업데이트한다.
    • next[next[i]]를 next[next[next[i]]]로 업데이트한다.
    • next[next[next[i]]]가 존재하면 그 노드의 prev를 next[i]로 설정한다.
• 변환으로 인해 새로운 'ABB' 패턴이 생길 수 있는 위치들을 큐에 추가한다:
  • prev[prev[i]], prev[i], i, next[i], next[next[i]] 위치 중 유효한 위치를 큐에 넣는다.
  • 해당 위치의 문자가 'A'이고 아직 큐에 없을 때만 추가한다.

4. 결과 문자열 생성

• 연결 리스트를 순회하여 최종 문자열을 생성한다.
• prev가 -1인 노드부터 시작하여 next를 따라가며 문자를 추가한다.

 

백준 32293 ABB to BA (Hard) 제출 결과

백준 32293 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.