알고스팟 jaehasafe C++ (재하의 금고)

2주동안 꿀같은 휴가를 다녀왔다ㅎㅎ

근데 코로나 시국이라서 휴가 복귀하고 2주동안 부대에서 격리를 해야한다.

당연히 싸지방에 갈 수 없었고, 종만북으로 이론공부도 하고 손코딩도 했다.

전역전에 300문제...는 이제 달성하기 힘든 목표가 되었지만 그래도 논다고 달성 못한것은 아니고, 이론공부도 하고 프로젝트도 해서 못한것이다 헣

어쨌든 오늘부터는 종만북(==알고리즘 문제 해결 전략)에 대한 문제를 풀 예정이다.

시간 제한	메모리 제한	정답률
1초	65MB	29%

문제 링크 : https://www.algospot.com/judge/problem/read/JAEHASAFE

algospot.com :: JAEHASAFE

Jaeha’s Safe 문제 정보 문제 문제 PDF 입력 . 출력 . 예제 입력 2 3 abbab babab ababb bbaba 2 RMDCMRCD MRCDRMDC DCMRCDRM 예제 출력 6 10 노트

www.algospot.com

문제 복붙이 안되는 관계로 링크를 건다.

백준은 복붙되어서 블로그 글쓰기 참 좋았는데...

핵심

brute force로 탐색하면 시간초과. 문자열 탐색은 kmp알고리즘 사용할 것
circular shift(환형 시프트)는 문자열+문자열에서 찾는 문자열을 검색하는 것으로 구현가능.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>


using namespace std;

int c, n, ans;
string tmp1, tmp2;
bool flag;

//kmp알고리즘 개량 버젼
vector<int> getPartialMatch(const string& N){
    int Nsize = N.size();
    vector<int> pi(Nsize, 0);
    
    //kmp로 자기자신을 찾는다.
    //N에서 N을 찾는다. begin=0이면 자기자신을 찾아버리기 때문에 1로 시작한다.
    int begin = 1, matched = 0;
    
    while(begin + matched < Nsize){
        if(N[begin+matched] == N[matched]){
            ++matched;
            pi[begin + matched - 1] = matched;
        }
        else{
            if(matched == 0){
                ++begin;
            }
            else{
                //이걸 계산할 때면 pi[matched - 1]은 항상 계산되어있음
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    
    return pi;
}

//kmp알고리즘 오리지널 버전. 알고리즘은 똑같음.
vector<int> kmpSearch(const string& H, const string& N){
    int Hsize = H.size();
    int Nsize = N.size();
    int matched = 0;
    
    vector<int> pi = getPartialMatch(N);
    vector<int> ret;
    
    for(int i=0;i<Hsize;i++){
        
        while(matched > 0 && H[i] != N[matched]){
            matched = pi[matched - 1];
        }
        
        if(H[i] == N[matched]){
            matched++;
            
            if(matched == Nsize){
                ret.push_back(i - Nsize + 1);
                matched = pi[matched - 1];
            }
        }
    }
    
    return ret;
}

int shifts(const string& original, const string& target){
    return kmpSearch(original + original, target)[0];
}


int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> c;
    
    while(c--){
        cin >> n;
        ans = 0;
        flag = false;

        cin >> tmp1;
        
        for(int i=0;i<n;i++){
            cin >> tmp2;
            
            
            if(flag) ans += shifts(tmp1, tmp2);
            else ans += shifts(tmp2, tmp1);
            tmp1 = tmp2;
            flag = !flag;
        }
        
        cout << ans << '\n';
    }
	
	return 0;
}