백준 15831번 준표의 조약돌

문제

그림1. 준표가 좋아하는 하얀색의 미미

준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.

준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.

1. 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
2. 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.

만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.

입력

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다.

출력

준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.

Small (100점)

• 1 ≤ N ≤ 3,000
• 0 ≤ B, W, B+W ≤ N

Large (150점)

• 1 ≤ N ≤ 300,000
• 0 ≤ B, W, B+W ≤ N

 

<윈도우 슬라이딩 기법>

처음에는 조건을 충족하거나 하지않는 경우에 대해서는 그냥 카운트 만 올려가면서 반복 되다가 조건이 충족되는 순간 resutlt(길이정보)를 갱신함. 그리고 다시 카운트를 하다가 조건이 불 총족 되는 순간 앞에서 부터 하나씩 해당 색에대한 카운트를 제거하면서 조건 불총족에서 벗어날때 까지 반복함 그러면 조건 불총족이 되는 지점까지 도달하는데 문제가 되지않는 시작 위치까지 제거됨. 그리고 나서 그 이후 부터 반복 함.

#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;

}

 

 

 

 

<내 코드>

 

오름차순 정렬이므로 operator방향 반대로 크루스칼 같이 최소비용은 그대로 사용.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int white, black, length;
bool check = false;

struct node{

int wc;
int bc;
int lc;

bool operator<(node const &e)
{
return lc > e.lc;
    }
};

vector <node>vec;


int main(void)
{


int N,w,b;
string str;

cin >> N >> b >> w;

cin >> str;

for(int i=0; i< str.size(); i++)
{
 white = 0;
 black = 0;
 length = 0;

for(int j = i; j < str.size(); j++)
{   

if(str[j] == 'W')
{
white++;
length++;
}
else if(str[j] == 'B')
{
black++;
length++;
}

if(black>b)
{   
    black--;
length--;
break;
}

}
vec.push_back({white,black,length});


}

sort(vec.begin(),vec.end());



for(int i =0; i < vec.size(); i++)
{
if(vec[i].wc>=w)
{
cout << vec[i].lc<<endl;
check = true;
break;

}

}
if(!check){
cout<<"0"<<endl;
}



}