[백준 15831] 준표의 조약돌 (Python)

www.acmicpc.net/problem/15831

15831번: 준표의 조약돌

 

문제풀이

N, B, W, arr : 입력값

w_cnt, b_cnt : 현재 수열에서 W와 B의 개수

q : 현재 수열

 

다른 투 포인터(Two-Pointer) 문제와 큰 차이 없는 문제였지만, 예외 케이스를 처리해줘야 하는 문제였다. 

6 0 0

BBBBBB

위와 같은 테스트케이스에서 q(현재 수열)에 들어갈 수 있는 값이 존재하지 않는데, q.popleft() 하기 떄문에 런타임 에러가 났다. 

 

1. 현재 수열에서 'B' 의 개수가 B 일때 까지 right 를 증가시키면서 q(현재 수열)에 원소를 삽입한다.

- b_cnt == B 인데, 추가로 arr[right] == B 이면 조건에 위배되므로 break를 해준다.

 

2. b_cnt <= B 이고 w_cnt >= W 이면 ans를 갱신한다.

 

3. 위에서 언급한 테스트케이스와 같은 경우의 예외처리를 해준다.

- q가 비어있기 때문에 곧바로 left, right를 1 증가해준다.

 

4. 3이 아닐 경우, 수열에서 가장 좌측의 값을 빼주고 해당하는 색상의 개수를 줄여준다.

 

코드

import sys
from collections import deque

if __name__ == '__main__':
    N, B, W = map(int, sys.stdin.readline().split())
    arr = list(map(str, sys.stdin.readline().rstrip()))

    left, right = 0, 0
    w_cnt, b_cnt = 0, 0
    q = deque()
    ans = 0
    while left < N and right < N:
        while right < N and b_cnt <= B:
            if b_cnt == B and arr[right] == 'B': break
            if arr[right] == 'B': b_cnt += 1
            else: w_cnt += 1
            q.append(arr[right])
            right += 1
        if b_cnt <= B and w_cnt >= W:
            ans = max(ans, len(q))
        if not q: # B 가 0 이고 BBBBB 와 같이 B가 연속적으로 들어오는 예외 상황 처리
            left += 1
            right += 1
            continue
        x = q[0]
        if x == 'B': b_cnt -= 1
        else: w_cnt -= 1
        q.popleft()
        left += 1
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!