[Silver V] 돌려 돌려 돌림판!

[문제 위치]

https://www.acmicpc.net/problem/11504

[문제 풀이]

 

이 알고리즘은 원형으로 된 돌림판에서 시작 위치를 바꿔가며 M자리의 숫자를 추출하고, 그 숫자가 주어진 범위 X 이상 Y 이하에 해당하는지를 판단하여 조건을 만족하는 경우의 수를 세는 방식이다. 먼저 입력으로 돌림판의 칸 수 N과 숫자의 길이 M, 그리고 범위의 시작값 X와 끝값 Y가 주어진다. X와 Y는 자릿수마다 분리되어 주어지기 때문에 이를 문자열로 변환하여 비교 연산에 사용할 수 있도록 처리한다.

 

그다음, 돌림판은 원형이므로 예를 들어 마지막 칸에서 시작해서 M개의 숫자를 추출하려면 처음으로 다시 돌아가야 하므로, 돌림판 숫자를 M−1칸만큼 뒤에 덧붙여 확장 배열을 만든다. 이렇게 하면 배열 범위를 벗어나지 않고도 어디에서나 M개의 숫자를 시계방향으로 추출할 수 있게 된다.

 

이제 0번 위치부터 N−1번 위치까지 가능한 모든 시작점을 기준으로 M개의 숫자를 추출하고, 이를 문자열로 만들어 Z라고 한다. 이 Z가 X 이상이고 Y 이하인지를 문자열 비교를 통해 판단한 뒤, 조건을 만족한다면 카운트를 증가시킨다. 문자열 비교를 사용하는 이유는 숫자가 0으로 시작할 수 있기 때문에 정수형으로 변환하면 값이 달라질 수 있기 때문이다.

 

결과적으로, 돌림판의 각 칸에서 시작해 만든 모든 M자리 숫자 중에서 X와 Y 사이에 속하는 숫자의 개수를 출력하면 된다. 이때 같은 숫자라도 시작 위치가 다르면 서로 다른 경우로 인정되므로 중복을 허용해 센다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N, M;
        cin >> N >> M;

        vector<int> X(M), Y(M), wheel(N);
        for (int i = 0; i < M; ++i) cin >> X[i];
        for (int i = 0; i < M; ++i) cin >> Y[i];
        for (int i = 0; i < N; ++i) cin >> wheel[i];

        string Xs, Ys;
        for (int d : X) Xs += char(d + '0');
        for (int d : Y) Ys += char(d + '0');

        vector<int> extended = wheel;
        extended.insert(extended.end(), wheel.begin(), wheel.begin() + M - 1);

        int count = 0;
        for (int i = 0; i < N; ++i) {
            string Z;
            for (int j = 0; j < M; ++j)
                Z += char(extended[i + j] + '0');
            if (Xs <= Z && Z <= Ys)
                ++count;
        }

        cout << count << '\n';
    }

    return 0;
}