[골드 3] 백준 25381 - ABBC (파이썬)

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

풀이

문자열 S가 주어지며, S에서 문자 B는 한번씩만 사용할 수 있다.

1. B앞에 A가 있으면 AB짝을 만든다.
2. B뒤에 C가 있으면, BC 짝을 만든다.

AB 또는 BC 쌍을 최대한 많이 만들어야하며, 단 하나의 B는 한번만 사용할 수 있다.

B의 위치를 저장하기 위해서 다음과 같이 정의한다.

queue = deque()
for i in range(len(S)) :
    if S[i] == 'B' :
        queue.append(i)

문자열에서 B의 인덱스 위치를 모두 deque에 저장하고, 앞뒤에서 모두 사용할 수 있게 deque를 사용한다.

다음은 BC를 매칭한다. (왼쪽 → 오른쪽)

for i in range(len(S)) :
    if S[i] == 'C' :
        if len(queue) != 0 and queue[0] < i :
            answer += 1
            queue.popleft()

C를 기준으로 앞에 있는 B가 있는 경우 BC 쌍으로 매칭한다.

가장 앞쪽 B부터 사용하며 queue.popleft로 제거한다.

다음은 AB 매칭을 진행한다. (오른쪽 → 왼쪽)

for i in range(len(S) - 1, -1 , -1) :
    if S[i] == 'A' :
        if len(queue) != 0 and queue[-1] > i :
            answer += 1
            queue.pop()

이번엔 A를 기준으로 뒤에 있는 B를 찾아 AB쌍을 만든다.

가장 뒤쪽 B부터 사용하며,queue.pop()으로 제거한다.

코드

# 백준 25381 - ABBC
# 분류 : 큐

from collections import deque

S = input()

queue = deque()
for i in range(len(S)) :
    if S[i] == 'B' :
        queue.append(i)

answer = 0
for i in range(len(S)) :
    if S[i] == 'C' :
        if len(queue) != 0 and queue[0] < i :
            answer += 1
            queue.popleft()

for i in range(len(S) - 1, -1 , -1) :
    if S[i] == 'A' :
        if len(queue) != 0 and queue[-1] > i :
            answer += 1
            queue.pop()

print(answer)