[Codeforces 1082B] Vova and Trophies

[Codeforces 1082B] Vova and Trophies

문제 설명 : 

n개의 'G'또는 'S'로만 이루어진 문자열이 주어진다. 여기서 연속된 'G'로만 이루어진 substring의 최대 길이를 구해야 하는데, 최대 한 번 문자열에서 아무 두 인덱스를 골라서 문자를 swap하는 것이 허용된다.

풀이 : 

swap하는 조건이 없다면 단순히 연속된 문자열의 개수가 몇 개인지 세면 될 것이다. 그런데 swap 조건이 끼어들어서 문제가 조금 까다로워졌다. 예를 들어서 문자열 "GGSGSG"가 있을 때 swap이 없다면 최대 길이는 2 지만, swap을 한다면 3번 째(S)와 6번 째(G)를 swap하면 최종적으로 "GGGGSS"가 되어서 최대 길이는 4가 된다. 이처럼 swap조건이 있을 때는 연속된 'G'로 이루어진 substring이 단 하나의 'S'로 인해서 끊겼을 때, 그 'S'를 'G'로 대체함으로써 끊어진 부분을 연결할 수 있다. 여기까지만 봤을 때는 'S'를 기준으로 (왼쪽 'G'의 최대 길이) + (오른쪽 'G'의 최대 길이) + 1 을 하면 답이 될 것처럼 보인다. 하지만 예외 케이스도 존재한다. 문자열 "GGSGG"의 경우 3번 째(S)를 1번 째 혹은 5번 째(G)와 swap하면 최대 길이는 4가 된다. 이런 케이스는 문자열에서 등장하는 'G'의 횟수가 곧 내가 연결한 'G'의 substring 횟수와 동일할 때 일어난다. 따라서 이 경우만 위의 언급한 공식에서 +1을 더해주는 과정만 생략해주면 된다.

주의할 점 : 

풀이에서 언급했다시피 예외 처리로서 전체 'G'의 등장 횟수와 substring에서의 'G'의 등장 횟수가 동일할 때를 주의해야 한다.

배운 점 : 

접근 방식에 따라서 쉽게 풀 수도 있고, 빙 돌아가면 어렵게 접근할 수도 있는 문제이다. 예외 케이스만 잘 처리하면 쉽게 풀 수 있을 것이다. 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE= 100009;
 
 
char str[SIZE];
int main(){
    int n;    scanf("%d",&n);
 
    scanf("%s",str+1);
 
    vector<int> v,vv;
    int cnt=0,total=0;
    for(int i=1 ; i<=n ; i++){
        if(str[i]=='G'){
            cnt++;
            total++;
        }
        else{
            v.push_back(cnt);
            cnt=0;
        }
    }    
    v.push_back(cnt);
 
    int ans=v[0];
    for(int i=0 ; i<v.size()-1 ; i++){
        ans=max(ans,v[i]+v[i+1]);
    }
    ans=min(total,ans+1);
    printf("%d\n",ans);
    return 0;
}