[BOJ 24525, 어려움] SKK문자열 (C++)

개인적인 난이도

어려움

 

시간많이걸렸다

누적합인거 늦게라도 알아서 풀었지 몰랐으면 못풀었을 것 같다

아이디어가 좋은 문제 같다

---

실패한 풀이 1)

8개월 전에 한거라 왜 이렇게 했는지도 모르겠다
일단 이때는 누적합 아이디어가 없었음

 

원형 큐를 이용해 풀이를 시도했다
원형 큐를 이용한다면 S1개 K2개인 경우는 찾아낼 수 있을지도 모르겠으나

K가 S개수의 2배가 되는 경우(문제의 조건)을 찾아낼 수 없다

문제를 잘못 읽었나 보다
아래의 코드는 그냥 보지 마라

 

실패 코드

//BOJ 24525 SKK문자열
//2022-05-02

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

int qq[3] = {-2,-2,-2}; // S=1와 K=0의 원형 큐
int qp = 0; //큐 위치

int resq[4] = {0,0,0,0}; // 결과 계산을 위한 원형 큐
int resp = 0; // 큐 위치

bool q_done(){  //SKK큐가 완성되었는가?
    if(qq[0]+qq[1]+qq[2]==1)return 1;
    else return 0;
}
void q_push(int a){   //SKK큐에 push
    qq[qp]=a;
    qp=(qp+1)%3;
}
void resq_push(int a){   //resq큐에 push
    resq[resp]=a;
    resp=(resp+1)%4;
}
int resq_sum(){ //resq 큐의 sum 계산
    return resq[0]+resq[1]+resq[2]+resq[3];
}

int skksolve(){
    string SKK;cin>>SKK;
    vector<int> res;
    int tmp=0;
    for(int i=0;i<SKK.length();i++){
        tmp++;
        if(SKK[i]=='S'){
            resq_push(tmp);
            if(q_done)res.push_back(resq_sum()-1);
            tmp=0;
            q_push(1);
        }
        else if(SKK[i]=='K'){
            resq_push(tmp);
            if(q_done)res.push_back(resq_sum()-1);
            tmp=0;
            q_push(0);
        }
    }
    resq_push(tmp);
    if(q_done())res.push_back(resq_sum());
    int tmpmax = -1;
    for(int i=0;i<res.size();i++){
        tmpmax = tmpmax<res[i]?res[i]:tmpmax;
    }
    return tmpmax;
}

int main(void){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cout<<skksolve()<<endl;
}

 

---

성공한 풀이)

S와 K의 등장 횟수를 누적합 배열로 저장하면서,
S는 2, K는 -1로 생각해 두개의 합이 0이 되면 K의 개수가 S의 개수의 2배가 된다

이런 아이디어가 필요함

그래서 S와 K의 누적합이 같아지는 끝부분과 끝부분을 찾아서 그 길이를 구하면 된다.

 

기하적으로 생각하면 이런 아이디어도 가능한데 괜히 이걸로 고민하다가 시간 더 걸렸다

기하적으로
y = S와 K의 누적합
x = 문자열의 인덱스
이렇게 생각하면 2차원 그래프와 y=n그래프의 교점을 구하는 문제처럼 생각해볼 수도 있겠다

이런 아이디어를 쓰는 문제도 어딘가 있지 않을까?

 

아무튼 성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;

int ssum[100001];
int ksum[100001];
int main(void)
{
    fastio;
    string s;cin>>s;
    map<int,int> mmin;
    map<int,int> mmax;
    int ans = 0;
    s = "-"+s;
    mmin.insert({0,0});
    for (int i = 1; i < s.length(); i++)
    {
        if(s[i]=='S')ssum[i]=ssum[i-1]+2;
        else ssum[i]=ssum[i-1];
        if(s[i]=='K')ksum[i]=ksum[i-1]+1;
        else ksum[i]=ksum[i-1];
        if(mmin.find(ssum[i]-ksum[i])==mmin.end())mmin.insert({ssum[i]-ksum[i],i});
        mmax[ssum[i]-ksum[i]]=i;
    }

    for(auto i:mmin){
        bool flg = 0;
        int ob = ksum[i.second];
        for (int j = i.second+1; j < mmax[i.first]; j++)
        {
            if(ksum[j]!=ob){
                flg = 1;
                break;
            }
        }
        if(flg)
        ans = max(ans,mmax[i.first]-mmin[i.first]);
    }
    if(ans<3||mmin.size()<3||ssum[s.length()-1]<1||ksum[s.length()-1]<2)cout<<-1;
    else cout<<ans;
    return 0;
}

map 2개를 이용해서, 어떤 누적합 값이 처음 등장하는 인덱스를 mmin에 저장하고
그 누적합 값이 마지막으로 등장하는 인덱스를 mmax에 저장한다.
문자열이 시작되는 부분은 누적합 값이 0이고 인덱스가 0인 것도 까먹지 말자

그럼 가능한 SKK문자열의 길이는 mmax-mmin으로 구할 수 있다

근데 함정이 있다 SKK문자열에 최소한 S 1개와 K 2개가 들어가있는지 확인해주는 과정이 필요하다
그렇지 않으면 SZZZZSSSKK 같은 입력의 정답을 5로 출력해버린다 그래서 몇번 삽질했다

 

문제 조건을 제대로 이해하지 않은 상태로 문제를 풀려다가 오래 걸렸고
누적합 아이디어가 없어서 오래 걸렸고
min 과 max를 map에 저장해 봐야겠다는 아이디어가 없어서 오래 걸렸다

좋은 문제 같다