[백준 15831번] 준표의 조약돌 (C++)

문제링크 : https://www.acmicpc.net/problem/15831

15831번: 준표의 조약돌

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main() 
{
   ios_base::sync_with_stdio(false); 
   cin.tie(0);

   int N, B, W;
   cin >> N >> B >> W;

   string s;
   cin >> s;

   int l = 0, r = 0, B_cnt = 0, W_cnt = 0;
   int result = 0;

   while(l<N)
   {
      if(W_cnt >= W && B_cnt <=B)
      {
         result = max(result, r-l); //조건에 맞는 길이저장
      }

      if (B_cnt > B)
      {
         if(s[l++] == 'B') B_cnt--; //왼쪽 인덱스 증가
         else W_cnt--;
      }
      else
      {
         if(r < N && s[r++] == 'W') W_cnt++; //오른쪽 인덱스 증가
         else B_cnt++;
      }
   }

   cout << result;

   return 0;
}

투포인터 문제다.

좌측 인덱스하나, 우측 인덱스 하나를 지정하고 조건에 맞게 인덱스들을 조정한다.

처음에 우측 인덱스를 움직여주면서 W와 B의 갯수를 카운트하다가 만약 B의 갯수가 주어진 제한 갯수를 넘어선다면 이제 왼쪽 인덱스를 움직여준다.

이때 왼쪽 인덱스의 값에 따라 왼쪽 인덱스가 이동하면서 값이 사라지기에 해당 값들의 갯수를 줄여준다.

이렇게 움직여가면서 왼쪽 인덱스가 총 길이인 N까지 이동하게되면 종료한다.

 

조건에 맞을때마다 최대 길이를 result에 저장하고 길이는 우측 인덱스 - 좌측 인덱스이다.