백준 15831번 준표의 조약돌

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

학회장님이신 malkoring 님한테 슬라이딩 윈도우 기법 설명을 듣고 풀어본 문제였습니다.

슬라이딩 윈도우 기법은 간단히 설명하자면 조건이 충족되는 구간만 확인하고 조건이 충족되지 않는다면 확인하는 구간(윈도우)를 한칸씩 옮겨가는 기법입니다!

자료구조는 push_back과 pop_front를 모두 지원해야하기 때문에 deque을 사용했습니다.

첫 번째 테스트 케이스를 예시로 간단히 설명하겠습니다.

주어진 산책로의 길이는 10이고 검은 조약돌은 1개까지만 줍고 흰 조약돌은 2개 이상 주워야 조건이 충족됩니다.

과정은 아래와 같습니다(주어진 산책로: WBBWWBWWBW)

1. W(white:1, black:0 조건 불충족)

2. WB(white:1, black:1 조건 불충족)

3. WBB(white:1, black:2 검은 조약돌은 1개까지만 허용되기 때문에 검은 조약돌이 1개가 될 때까지 이미 주운 조약돌을 버립니다.) 

-> B(white:0, black:1)

4. BW(white:1, black:1 조건 불충족)

5. BWW(white:2, black:1 조건 충족, 현재 최고 길이: 3)

6. BWWB(white:2, black:2 3번과 마찬가지로 앞에 조약돌을 버립니다.)

->WWB(white:2, black:1 조건 충족, 현재 최고 길이: 3)

7. WWBW(white:3, black:1 조건 충족, 현재 최고 길이: 4)

8. WWBWW(white:4, black:1 조건 충족, 현재 최고 길이: 5)

9. WWBWWB(white:4, black:2 3번과 마찬가지로 앞에 조약돌들을 버립니다.)

->WWB(white:2, black:1 조건 충족, 현재 최고 길이: 5)

10. WWBW(white:3, black:1 조건 충족, 현재 최고 길이: 5)

#include <iostream>

#include <string>

#include <deque>

#include <algorithm>

using namespace std;

 

int N, B, W;

string S;

deque<char> dq;

 

int maxLength(void)

{

        int black = 0, white = 0;

        int result = 0;

 

        for (int i = 0; i < N; i++)

        {

                 dq.push_back(S[i]);

                 if (S[i] == 'B')

                         black++;

                 else

                         white++;

 

                 //조건 충족 시

                 if (black <= B && white >= W)

                         result = max(result, (int)dq.size());

                 //조건 불충족할 경우

                 else if (black > B)

                 {

                         //조건 불충족하는 동안

                         while (black > B)

                         {

                                 //슬라이딩 윈도우 기법

                                 char c = dq.front();

                                 dq.pop_front();

                                 if (c == 'W')

                                          white--;

                                 else

                                          black--;

                         }

                 }

        }

        return result;

}

 

int main(void)

{

        cin >> N >> B >> W;

        cin >> S;

 

        cout << maxLength() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~