[C++] 10266번 시계 사진들 - 문자열, KMP

1. 문제

• 상근이는 두 시계 사진을 가지고 있다. 각 사진은 동일한 길이와 목적을 가진 n개의 시곗바늘을 가지고 있는데 각 시곗바늘의 위치만 구분할 수 있고 가리키는 곳이 어디인지는 알 수 없다. 이때 한 시계 사지을 돌려 다른 시계 사진과 일치시킬 수 있는지를 확인하시오.

<입력>

• -1-   바늘의 수 $n(2\le n\le 200,000)$
• -2, 3-   n개의 상수 $a_i(0\le a_i<360,000)$이 주어지며 이는 각 사진에서 바늘의 시계 각도를 나타낸다. 바늘의 각도는 특정 순서대로 주어지지 않으며 한 줄에는 같은 각도값이 두 번 이상 주어지지 않는다.

<출력>

• 두 시계 사진이 돌려서 같다면 possible을, 그렇지 않다면 impossible을 출력하라.

2. 재정의

• 문자열이 순환해서 다른 문자열과 같아지는지를 확인하기

3. 해결 방법

• 두 문자열(int 형)을 받는다.
• 두 문자열의 차이로 문자열을 만든다.
• kmp를 진행하면서 시작 번째부터 끝까지 같은 부분을 찾는다.
• 남은 부분과 앞 부분을 비교한다.
• 이것까지 같으면 possible
• 끝까지 남은 부분이 없거나 남은 부분과 앞부분이 다른 경우 impossible

4. 실수한 점, 개선할 점

• 변수 초기화 시켜주기
• 두 문자열에 있는 숫자의 차이가 음수로 계산될 수 있음.
• 차이를 구하지 않고 index=각도에 1을 넣고 각도+360,000에도 1을 넣어줌으로써 kmp 한 번으로 구할 수 있음. 이렇게 푼 코드가 있어서 아래에 링크했다.

 

<코드>

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

using namespace std;

const int MAX_N = 360001;

//바늘의 수 n
int n;
//바늘의 시계 방향 각도
int str1[MAX_N], str2[MAX_N];
//KMP용 두 문자열
int text[MAX_N], pattern[MAX_N];

void input() {
    cin >> n;
    
    for(int i=0; i<n; i++)
        cin >> str1[i];
    sort(str1, str1+n);
    
    for(int i=0; i<n; i++)
        cin >> str2[i];
    sort(str2, str2+n);
    
    for(int i=0; i<n-1; i++)
        text[i] = str1[i+1]-str1[i];
    text[n-1] = str1[0] - str1[n-1];
    if(text[n-1] < 0) text[n-1] += 360000;
    
    for(int i=0; i<n-1; i++)
        pattern[i] = str2[i+1] - str2[i];
    pattern[n-1] = str2[0] - str2[n-1];
    if(pattern[n-1] < 0) pattern[n-1] += 360000;
}

vector<int> Fail(int pattern[]) {
    int m = 0;
    for(int i=0; pattern[i]; i++) { m++; }
    vector<int> pi(m);
    
    pi[0] = 0;
    for(int i=1, j=0; i<m; i++) {
        while(j>0 && pattern[i]!=pattern[j]) j = pi[j-1];
        if(pattern[i] == pattern[j]) pi[i] = ++j;
    }
    return pi;
}

int KMP(int text[], int pattern[]) {
    //pattern과 text의 문자열 길이
    int m, n;
    m = n = 0;
    for(int i=0; pattern[i]; i++) { m++; }
    for(int i=0; text[i]; i++) { n++; }
    
    vector<int> pi = Fail(pattern);
    
    int i, j;
    
    for(i=0, j=0; i<n; i++) {
        while(j>0 && text[i]!=pattern[j]) j = pi[j-1];
        if(text[i] == pattern[j]) {
            if(j == m-1)
                return -1;
            j++;
        }
    }
    
    
    return j;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    
    int p = KMP(text, pattern);
    if(KMP(text, pattern+p) == -1)
        cout << "possible";
    else
        cout << "impossible";
    
    return 0;
}

 

 

<더 가벼운 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/17745439

로그인

 

<KMP 알고리즘>

https://ansohxxn.github.io/algorithm/kmp/

(C++) 문자열 검색 알고리즘 : KMP 알고리즘

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.