[baekjoon] 24525

SKK 문자열 

문제

포함된 K의 개수가 S의 개수의 정확히 2$2$배이면서, S와 K가 적어도 한 번은 등장하는 문자열을 SKK 문자열이라고 한다.

SKK 문자열은 S, K 말고도 다른 알파벳 또한 포함할 수 있다.

알파벳 대문자로만 이루어진 문자열 �$S$가 주어질 때, �$S$의 부분 문자열 중 길이가 가장 긴 SKK 문자열을 찾는 프로그램을 작성하라.

입력

첫째 줄에 길이가 1$1$이상 100,000$100,000$ 이하인 알파벳 대문자로만 이루어진 문자열 �$S$가 주어진다. 

출력

 S의 부분 문자열 중 길이가 가장 긴 SKK 문자열의 길이를 출력한다. 만약 그러한 문자열이 없으면 -1을 출력한다.

풀이

S + K + K = 0 이 되게끔 S와 K의 값을 설정해 준다. 나는 S : 2, K : -1, 이 외의 문자 : 0으로 했다.

이렇게 해주는 이유는 SKK 문자열이란 S 1개당 K가 2개가 포함되는 문자열이기때문이다.

 

규칙 1. 누적합[a] - 누적합[b-1] = 0 이면 b~a는 SKK 문자열이다. (이유는 해당 구간의 합이 0이기 때문이다.)

규칙 1을 바꿔보면 누적합[a] = 누적합[b-1] 이면 b~a는 SKK 문자열이란 거다.

 

누적합[a] = 누적합[b-1]인 좌표들을 기록하고

이때 문제에서 원하는 답은 가장 긴 SKK 문자열 이기 때문에 시작점은 가장 작은 값과 종료점은 가장 큰 값을 저장한다.

 

누적합이 같은 구간들 중 좌표의 차가 가장 큰 값이 답이 된다.

 

#include <iostream>
#include <string>
#include <cstring>

#define MAX 100000
#define MAX_RANGE 300000
using namespace std;

pair<int, int> smap[MAX_RANGE]; // 누적합 N에 대한 {minIdx, maxIdx}

void solve(){
    string s;
    int chStr[MAX]; // K는 -1, S는 2, 이외에는 0 으로 변환할 배열
    int sum[MAX], kcnt[MAX], scnt[MAX]; // 누적합, K의 개수 누적합, S의 개수 누적합
    bool check[MAX_RANGE]; // 누적합 N 에 대한 방문 검사, 최초 방문의 경우 최소 인덱스로 등록하고 이후에는 최대 인덱스로 등록 
    int length;
    cin >> s;
    
    length = s.length();

    //처음 입력인지 아닌지 검사하는 check 배열 초기화
    memset(check, false, sizeof(check));
    memset(kcnt, 0, sizeof(kcnt));
    memset(scnt, 0, sizeof(scnt));
    
    //누적합 0에 대한 초기화
    //SKK 와 같은 경우에 필요, SKK의 누적합은 -2 -1 0 이되는데 누적합 0에 대한 최소 인덱스를 임의로 -1로 설정.
    check[MAX] = true;
    smap[MAX] = {-1, -1};
    for(int i = 0; i < length; i++){
        if(s[i] == 'K')chStr[i] = -1;
        else if(s[i] == 'S')chStr[i] = 2;
        else chStr[i] = 0;
        
        //K 와 S의 누적합
        //AASKSSK 같은 경우 AA 를 답으로 처리하지 않기 위해 
        kcnt[i] = (i == 0 ? s[i] == 'K' : kcnt[i-1] + (s[i] == 'K'));
        scnt[i] = (i == 0 ? s[i] == 'S' : scnt[i-1] + (s[i] == 'S'));
        
        sum[i] = chStr[i] + (i != 0 ? sum[i-1] : 0);
        int idx = sum[i] + MAX;
        //첫 입력이면 최소값으로 등록
        if(!check[idx]){
            check[idx] = true;
            smap[idx] = {i, -1};
        }else{
            int tmp = smap[idx].first;
            smap[idx] = {tmp, i};
        }
    }
    //S와 K가 등장하지 않은경우
    if(scnt[length-1] < 1 || kcnt[length-1] < 2){
        cout << -1;
        return;
    }
    int answer = -1;

    for(int i = 0; i < MAX_RANGE; i++){
        if(!check[i])continue;
        int from = smap[i].first;
        int to = smap[i].second;

        if(to == -1)continue;
        else if(scnt[from] - scnt[to-1] != 0 && kcnt[from] - kcnt[to-1] != 0)answer = max(to - from, answer);
        
    }
    cout << answer;
}


int main(){
    solve();
}