1. Sliding Window란?

window를 한칸씩 움직이면 (W-1)칸이 겹친다.
창문을 옮길 때마다 W 개를 전부 다 더하는 작업을 말고, 이전의 결과를 써먹는 방향으로 접근하자.

2. 투포인터

알고리즘 순서
1. 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트 한다.
3. 현재 부분 합이 M보다 작거나 같으면, end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

3. 문제

준표의 조약돌

1. 문제

15831번: 준표의 조약돌

2.

아이디어

• 1 ≤ N ≤ 300,000

• 0 ≤ B, W, B+W ≤ N

  투포인터 시간복잡도

O(N)

3-1. 코드

처음 시도

1) 오른쪽 인덱스를 일단 늘려줌 늘려주고 시작하면 안된다!

오른쪽 인덱스를 들려주는 것은 while 문의 마지막으로 옮겨준다.

2) 검은 색 갯수 검사하고, 검은 색이 많으면 왼쪽 인덱스를 검은색이 나올 때까지 늘려줌

→ 투포인트 알고리즘은 왼쪽과 오른쪽을 한번씩만 증가 시키고, 확인해주어야 한다.

N, B, W = map(int, input().split())

graph = list(map(str,input()))

left = 0
right = 0
black = 0
white = 0
answer = float("-Inf")

while True:
    right += 1 
    if graph[right] == "W":
        white+=1
    else:
        black += 1
    
    if black > B: 
        for k in range(left, right):
            if graph[k] != 'B':
                left += 1
                white -= 1
            elif graph[k] == "B":
                left += 1
                black -= 1
                break
    
    if white >= W and black <= B:
        answer = max(answer, right - left + 1)
    
    if right == N-1:
        break
    

고친 풀이!

N, B, W = map(int, input().split())

graph = list(map(str,input()))

left = 0
right = 0
black = 0
white = 0
answer = float("-Inf")

while right < N:
    if graph[right] == "W":
        white+=1
    else:
        black += 1
    
    if black > B: ## 이 알고리즘의 문제점 black이 나오면 끝내야 한다. 하지만 계속 돌아간다.
        for k in range(left, right):
            if graph[k] != 'B':
                left += 1
                white -= 1
            elif graph[k] == "B":
                left += 1
                black -= 1
                break
    
    if white >= W and black <= B:
        answer = max(answer, right - left + 1)
    
    right += 1
    
    
    
if answer == float("-Inf") :
    print(0)
else:
    print(answer)