백준[10266] 시계 사진들

문제 설명

풀이

z알고리즘을 이용하여 풀이할 수 있다.

정수의 범위로 배열을 만들고 입력받는 숫자를 인덱스로 하여 그 부분을 1로 만들고 첫 번째 배열에서 두 번째 배열이 있는지 확인하는 문제다. 이때 시계가 원형이기 때문에 a를 2번 이어 붙인 배열의 부분 배열에 b배열이 있는지 찾는다.

cf) 배열을 이어 붙일 때 편의를 위해 배열을 string으로 만들어 + 연산자를 사용했다.

코드

#include <cstdio>
#include <string>

using namespace std;

const int MAX = 360000;

string a, b;
int Z[3 * MAX + 5];

void getZ(const string &str) {
    int L = 0, R = 0;
    int N = str.size();
    for (int i = 1; i < str.size(); i++) {
        if (R < i) {
            L = R = i;
            while (R < N && str[R - L] == str[R]) R++;
            Z[i] = R - L; R--;
        } else {
            int k = i - L;
            if (Z[k] < R - i + 1) Z[i] = Z[k];
            else {
                L = i;
                while (R < N && str[R - L] == str[R]) R++;
                Z[i] = R - L; R--;
            }
        }
    }
}

int main() {
    int N; scanf("%d", &N);
    //string을 배열처럼 사용하기 위해 resize 후 0으로 초기화
    a.resize(MAX); b.resize(MAX);
    for (int i = 0; i < MAX; i++) a[i] = b[i] = '0';

    for (int i = 0; i < N; i++) {
        int idx; scanf("%d", &idx);
        a[idx] = '1';
    }
    for (int i = 0; i < N; i++) {
        int idx; scanf("%d", &idx);
        b[idx] = '1';
    }
    // a를 두번 이어붙힘
    a += a;
    string concat = b + "$" + a;
    getZ(concat);
    
    bool flag = false;
    for (int i = 0; i < concat.size(); i++) {
        if (Z[i] >= b.size() - 1) flag = true;
    }
    if (flag) printf("possible");
    else printf("impossible");
}

문제 링크: https://www.acmicpc.net/problem/10266