알고스팟 문제 링크: 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

문자열을 시계 방향, 반시계 방향 번갈아가면서 시프트하여 목표하는 문자열과 일치하려 했을때 필요한 최소 시프트 횟수를 구하는 문제이다.

 

문자열의 일치는 kmp알고리즘(유명하고 많이 쓰이는 알고리즘이지만 이해하기 다소 어렵다,,,)을 이용하여 풀 수 있다.

현재 문자열을 시계 방향으로(오른쪽으로) 시프트 해서 다음 문자열과 일치할때의 최소 시프트 횟수를 알고 싶다면,

다음 문자열을 두개 이어붙인 문자열과 현재 문자열을 kmp알고리즘으로 비교하면 된다.

이때 kmp알고리즘에서 나오는 벡터의 첫번째 요소가 최소 시프트 횟수가 된다.

반시계 방향으로(왼쪽으로) 시프트 해서 다음 문자열과 일치하는것은

현재 문자열을 두개 이어붙이것을 다음 문자열이 오른쪽으로 시프트하는것을 비교하여 일치할때의 시프트 횟수를 찾으면 된다.

즉, 반시계 방향일때는 shifts 함수의 매개변수 순서만 바꿔주면 된다.

 

#include<iostream>
#include<vector>
using namespace std;
// kmp알고리즘을 위한 실패함수
vector<int> getPartialMatch(const string& N) {
int m = N.size();
vector<int> pi(m, 0);
int begin = 1, match = 0;
// 비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록
while (begin + match < m) {
if (N[begin + match] == N[match]) {
match++;
pi[begin + match -1] = match;
}
else {
if (match == 0)
begin++;
else {
begin += match - pi[match - 1];
match = pi[match - 1];
}
}
}
return pi;
}
// kmp 알고리즘
vector<int> kmpSearch(const string& H, const string& N) {
int n = H.size(), m = N.size();
vector<int> ret;
vector<int> pi = getPartialMatch(N);
int matched = 0;
// 문자열 H를 순회
for (int i = 0; i < n; i++) {
// 해당 위치에서 불일치 할경우 matched를 pi[matched-1]로 줄인다
while (matched > 0 && H[i] != N[matched])
matched = pi[matched - 1];
// 글자가 대응될 경우
if (H[i] == N[matched]) {
matched++;
if (matched == m) {
ret.push_back(i - matched + 1);
matched = pi[matched - 1];
}
}
}
return ret;
}
// 시계방향의 경우 현재 다이얼을 오른쪽으로 이동시키면서
// 목표하는 다이얼 모양을 나타내는 문자열 두개를 이어붙인것과
// 일치하는 처음 위치를 찾는다. (반시계 방향일 경우 target과 origin만 바꾸면 된다.)
int shifts(const string& target, const string& origin) {
return kmpSearch(target + target, origin)[0];
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n, ret = 0;
// 처음에는 시계방향
bool dir = false;
cin >> n;
string ori, tar;
cin >> tar;
for (int i = 0; i < n; i++) {
ori = tar;
cin >> tar;
if (dir)
ret += shifts(ori, tar);
else
ret += shifts(tar, ori);
dir = !dir;
}
cout << ret << endl;
}
}

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/20.%20string/JAEHASAFE.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

+ Recent posts