[백준 10266] 시계 사진들 (C#, C++) - soo:bak

문제 링크

10266번 - 시계 사진들

설명

두 시계의 바늘 위치가 주어질 때, 한 시계를 회전시켜서 다른 시계와 똑같이 만들 수 있는지 판별하는 문제입니다. 각도는 0부터 359,999까지의 정수로 표현됩니다.

접근법

회전으로 일치하는지 확인하는 것은 원형 문자열 매칭 문제와 같습니다. 시계를 돌린다는 것은 모든 바늘 각도에 같은 값을 더하는 것이고, 이는 문자열을 회전시키는 것과 동일합니다.

먼저 각 시계를 길이 360,000의 문자열로 표현합니다. 모든 위치를 0으로 채운 뒤, 바늘이 있는 각도 위치에만 1을 표시합니다. 이렇게 하면 두 시계가 각각 하나의 문자열이 됩니다.

원형 문자열에서 패턴을 찾으려면 텍스트를 두 번 이어붙이는 방법을 사용합니다. 예를 들어 문자열 “ABCD”의 모든 회전은 “ABCDABCD”의 부분 문자열로 나타납니다. “BCDA”는 위치 1에서, “CDAB”는 위치 2에서 시작합니다. 따라서 첫 번째 시계 문자열을 패턴으로, 두 번째 시계 문자열을 두 번 이어붙인 것을 텍스트로 두고 KMP 알고리듬으로 패턴이 등장하는지 찾으면 됩니다.

패턴이 발견되면 회전으로 일치할 수 있으므로 possible을, 발견되지 않으면 impossible을 출력합니다.

---

Code

C#

using System;

class Program {
  const int LEN = 360000;

  static int[] BuildPi(string pat) {
    var pi = new int[pat.Length];
    var j = 0;
    for (var i = 1; i < pat.Length; i++) {
      while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
      if (pat[i] == pat[j]) pi[i] = ++j;
    }
    return pi;
  }

  static bool Kmp(string pat, string txt, int[] pi) {
    var j = 0;
    for (var i = 0; i < txt.Length; i++) {
      while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
      if (txt[i] == pat[j]) {
        if (j == pat.Length - 1) return true;
        else j++;
      }
    }
    return false;
  }

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var a = new string('0', LEN).ToCharArray();
    var b = new string('0', LEN).ToCharArray();

    var parts = Console.ReadLine()!.Split();
    for (var i = 0; i < n; i++) a[int.Parse(parts[i])] = '1';
    parts = Console.ReadLine()!.Split();
    for (var i = 0; i < n; i++) b[int.Parse(parts[i])] = '1';

    var pat = new string(a);
    var txt = new string(b) + new string(b);
    var pi = BuildPi(pat);
    Console.WriteLine(Kmp(pat, txt, pi) ? "possible" : "impossible");
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

const int LEN = 360000;

vi buildPi(const string& pat) {
  vi pi(pat.size(), 0);
  int j = 0;
  for (int i = 1; i < (int)pat.size(); i++) {
    while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
    if (pat[i] == pat[j]) pi[i] = ++j;
  }
  return pi;
}

bool kmp(const string& pat, const string& txt, const vi& pi) {
  int j = 0;
  for (int i = 0; i < (int)txt.size(); i++) {
    while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
    if (txt[i] == pat[j]) {
      if (j == (int)pat.size() - 1) return true;
      else j++;
    }
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  string a(LEN, '0'), b(LEN, '0');
  for (int i = 0; i < n; i++) { int x; cin >> x; a[x] = '1'; }
  for (int i = 0; i < n; i++) { int x; cin >> x; b[x] = '1'; }

  string txt = b + b;
  vi pi = buildPi(a);
  cout << (kmp(a, txt, pi) ? "possible" : "impossible") << "\n";

  return 0;
}