🚀 [JAEHASAFE] 문제 😊😊😊😊😊
일곱 살 재하는 이번에 소중한 물건들을 보관하기 위해 어린이용 금고를 샀습니다. 재하의 취향에 맞춰 다이얼의 둘레에는 숫자가 아니라 여러 가지 동물들이 그려져 있습니다. 금고를 열기 위해서는 다이얼을 방향을 번갈아 가며 정해진 위치까지 돌려야 합니다.
위 그림의 예에서 세 다이얼은 각각 다이얼의 현재 상태, 시계 방향으로 돌려서 나와야 하는 상태, 시계 반대 방향으로 나와야하는 상태를 가리킵니다. 따라서 시계 방향으로 네 칸, 시계 반대 방향으로 여섯칸을 돌리면이 금고를 열 수 있습니다.
재하는 아빠를 닮아서 성격이 급합니다. 다이얼의 현재 상태와 금고를 여는 방법이 주어졌을 때, 금고를 열기 위해서는 다이얼을 최소 몇 칸 돌려야 할가요?
🔑 [풀이]
시계 반대방향에 대해서는 다이얼을 돌리는 것을 트릭으로 이전의 문자열을 두배로 연장하여 그속에서 다음 문자열을 찾습니다.
kmpSearch 를 이용하여 두배로 연장한 문자열 속에서 다음 문자열이 포함되는 위치중 최소인 [0] 을 리턴합니다.
시계 방향에 대해서는 original과 target을 반대로 주어 위와 같이 해결한다.
함수에 대한 내용은 코드 참고.
⌨️ 입력
입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 금고를 열기 위해 맞춰야 하는 상태의 수 N(1<=N<=100)이 주어집니다.
그 다음 N+1줄에 각 하나씩 금고 다이얼의 상태가 주어집니다. 다이얼의 상태는 맨 위에부터 시계방향으로 각 칸에 어떤 그림이 그려져있는지로 주어집니다.
알파벳은 소문자 혹은 대문자로 표현되고, 각 상태는 다이얼의 칸 수를 길이로 하는 문자열입니다. 문자열의 길이는 10000 이하의 자연수입니다.
- 첫 번째 상태는 현재 다이얼 상태
- 두 번째 상태는 시계방향으로 돌린 상태
- 세 번째 상태는 시계 반대방향으로 돌린 상태
- 그 다음에는 방향을 반대로해 반복합니다.
- 마지막 상태에 도달하면 금고가 열린다.
- 연속적으로 같은 상태가 주어지는 경우는 없다.
🖥 출력
최소 몇 칸을 돌려야 금고를 열수 있는지 출력한다. 열수 없는 경우는 없다.
🖱 입력 예제
2
3
abbab
babab
ababb
bbaba
2
RMDCMRCD
MRCDRMDC
DCMRCDRM
💻 출력 예제
6
10
💎 전체 코드는 다음과 같습니다.
//
// JAEHASAFE.cpp
// AALGGO
//
// Created by inhyeok on 2021/12/03.
//
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("JAEHASAFE.txt");
vector<int> getPartialMatch(const string& N){
int m = N.size();
vector<int> pi(m,0);
// KMP 로 자기 자신을 찾는다
// N을 N에서 찾는다. begin = 0 이면 자기 자신을 찾아버리니깐 안됨!
int begin =1, matched = 0;
while(begin+matched < m){
if(N[begin+matched] == N[matched]){
matched++;
pi[begin + matched-1] = matched;
}
else{
if(matched == 0){
begin++;
}
else {
begin += matched - pi[matched-1];
matched = pi[matched-1];
}
}
}
return pi;
}
// H 속에서 N이 출현하는 시작 위치를 모두 반환한다.
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 begin = 0, matched=0;
while(begin + m <= n){
// 짚더미의 H의 해당 글자가 N의 해당글자가 같을때
if(matched < m && H[begin+matched] == N[matched]){
matched++;
// N의 글자가 H에 포함된다면
if(matched == m){
ret.push_back(begin);
}
}
else{
if(matched==0) begin++;
else{
begin += matched - pi[matched-1];
matched = pi[matched-1];
}
}
}
return ret;
}
int shifts(const string& original, const string& target){
// original+original 속에서 target 을 포함하는 가장 짧은 위치 index->0
return kmpSearch(original + original,target)[0];
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
int N;
fin >> N;
vector<string> vec(N+1);
for(int i=0; i<N+1; i++){
fin >> vec[i];
}
int count = 0;
for(int i=0; i<N; i++){
// 변화기 전과 후의 위치를 바꿔 찾는다.
if( i%2 == 0){ // 시계방향
count += shifts(vec[i+1], vec[i]);
}
else{ // 시계 반대방향
count += shifts(vec[i], vec[i+1]);
}
}
cout << count << endl;
}
}
Comments