[Python/파이썬] 백준 15831번 준표의 조약돌

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

코드

n, b, w = map(int, input().split())
pebbles = input()

answer = 0
left, right = 0, 0
count = dict([("B", 0), ("W", 0)])
count[pebbles[left]] += 1
while right < n:
    if count["B"] <= b and count['W'] >= w:
        answer = max(answer, right-left+1)
    right += 1
    if right > n-1:
        break
    count[pebbles[right]] += 1
    while count['B'] > b:
        count[pebbles[left]] -= 1
        left += 1

print(answer)

 

준표는 연속된 구간에서만 돌을 줍는다. 그러니까 0 ~ N까지의 구간이 있다고 할 때, 2 ~ 5까지 돌을 줍는 경우는 있어도 1 ~ 3까지 돌을 줍고, 또 4 ~ 5까지 돌을 줍는 경우는 없다는 말이다.

 

이런 경우에는 투포인터를 사용하면 문제를 풀 수 있다. 왼쪽 시작 지점과 오른쪽 끝점을 움직여가며 그 사이 구간의 돌 개수를 세어서 조건을 만족하며 가장 긴 구간이 되는 경우를 찾으면 된다.

 

left와 right는 각각 왼쪽 끝과 오른쪽 끝을 의미하고, 초기값은 둘 다 0이다. 우리는 left와 right 사이의 흰색 돌의 개수와 검은 돌의 개수를 count라는 딕셔너리에 저장한다.

변수는 이렇게 설정해두고 while문을 이용하여 right가 n보다 작은 동안 다음 과정을 반복한다.

1. left~right 구간의 검은 돌의 개수(`count['B']`)가 b보다 작거나 같고, 흰 돌의 개수(`count['W']`)가 w보다 크거나 같은 경우, 정답 조건을 만족하므로 현재 구간의 길이와 answer를 비교하여 둘 중 큰 값을 answer에 저장한다.

2. 오른쪽 끝(right)를 한 칸 오른쪽으로 이동한다.

3. 만약 현재 검은 돌의 개수가 b보다 많다면 b 이하가 될 때까지 왼쪽(left)를 오른쪽으로 당기는 작업을 반복한다.

 

이 while문을 다 돌고 나면 조건을 만족하면서도 최장 거리인 구간의 길이를 구할 수 있다. 만약 조건을 만족하는 구간이 없었다면 answer의 초기값인 0이 출력된다.