[문자열] JAEHASAFE 재하의 금고

1. 문자열

 

이 문제는 KMP알고리즘을 사용하면 간단하게 풀 수 있다.

 

아래 코드는 좀 복잡하게 구현하였는데,

사실 첫 상태와 비교하는게 아니라 이전 상태랑 비교하면

더 깔끔한 코드가 될 것이다.

 

또한 A를 시계방향으로 i만큼 돌린 결과가 B일때

이는 B를 반시계방향으로 i만큼 돌린 결과가 A라는

것을 이용하면 더 직관적 일 것이다.

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
int c;
int n;
string* strs;
 
int safe(int step, int top, int cw)
{
    if(step == n+1) return 0;
 
    int length = strs[step].length();
    int tmp = -1;
    int count = 0;
    int minCount = 1234567;
    int minTop = top;
    while( -1 != (tmp = strs[0].find(strs[step], tmp + 1)))
    {
        if(tmp == length) break;
 
        if(cw == -1)
        {
            if(top > tmp)
                count = top - tmp;
            else
                count = length - tmp + top; 
        }
        else
        {
            if(top < tmp)
                count = tmp - top;
            else
                count = length - top  + tmp; 
        }
        if(minCount > count)
        {
            minCount = count;
            minTop = tmp;
        }
 
    }
    return minCount + safe(step+1, minTop, cw*-1);
 
}
int main()
{
    cin>>c;
    for(int i = 0; i < c; i++)
    {
        cin>>n;
        strs = new string[n+1];
        for(int j = 0; j< n+1; j++)
        {
            cin>>strs[j];
        }
        strs[0] = strs[0] + strs[0];
        cout<<safe(1, 0, -1)<<'\n';
        delete[] strs;
    }
        
}

JAEHASAFE