백준 20442 : ㅋㅋ루ㅋㅋ

20442번: ㅋㅋ루ㅋㅋ (acmicpc.net)

20442번: ㅋㅋ루ㅋㅋ

풀이
R로만 이루어져있거나 R이 하나이상이고 양쪽에 같은수의 K가 있다면 ㅋㅋ루ㅋㅋ 문자열이다.
가운데 R을 기준으로 양쪽의 K 개수 중 작은 쪽을 기준으로 양쪽에 붙여서 만들 수 있음
투포인터를 이용하여 풀이
항상 k의 개수가 작은 쪽 부터 인덱스를 증감시킨다. k가 큰곳부터 움직인다고 해서 양쪽에 붙일 수 있는 k의 개수가 바뀌지않기 때문에 큰곳부터 움직이면 무조건 작아지기만 하므로 작은곳부터 움직여야한다.

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

int main() {
    init();
    string s; cin >> s;
    char ridx = (s[0] == 'R' ? 0 : 1);
    int cnt = 1;
    int ans = 0;
    int cntr = (s[0] == 'R' ? 1 : 0);
    vector<int> v;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] != s[i - 1]) {
            v.push_back(cnt);
            cnt = 1;
        }
        else cnt++;

        if (s[i] == 'R') {
            cntr++;
        }
    }
    v.push_back(cnt);

    int low = 0;
    int top = v.size() - 1;
    int lowk = 0;
    int topk = 0;
    while (low < top) {
        int len = cntr + min(lowk, topk) * 2;
        ans = max(ans, len);

        if (lowk < topk) {
            if (low % 2 == ridx) {
                cntr -= v[low++];
            }
            else {
                lowk += v[low++];
            }
        }
        else {
            if (top % 2 == ridx) {
                cntr -= v[top--];
            }
            else {
                topk += v[top--];
            }
        }
    }
    if (cntr != 0) {
        ans = max(ans, cntr + min(lowk, topk) * 2);
    }
    cout << ans << "\n";
}