[C++]백준 - 10266번 문제

10266번: 시계 사진들 (acmicpc.net)

10266번: 시계 사진들

 

10266번 : 시계 사진들

---

상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바늘들의 위치만 구분 할 수 있습니다.

우리의 상근이는 두 사진의 시계가 같은 시각을 나타낼 수 있는지 궁금해져 각 사진을 서로 다른 각도로 돌려보려고 합니다.

두 사진에 대한 묘사가 주어질 때, 두 사진의 시계가 같은 시각을 나타내는지 결정하세요.

 

입력

---

첫 줄에는 바늘의 수를 나타내는 정수 n(2 ≤ n ≤ 200 000)이 주어진다.

다음 두 줄에는 각각 n개의 정수가 주어지며, 주어지는 정수 ai(0 ≤ ai < 360,000)는 각 사진에서 바늘의 시계 방향 각도를 나타낸다. 이때 바늘의 각도는 특정 순서대로 주어지지는 않는다. 한 줄에는 같은 각도값이 두 번 이상 주어지지 않는다. 즉, 한 시계 안의 모든 각도값은 서로 구분된다.

 

 

출력

---

두 시계 사진이 같은 시각을 나타내고 있다면 "possible"을 아니면 "impossible"을 출력하시오.

 

---

 

생각해 볼 점

---

0 이상 36만 미만의 각도를 입력받아, 시계 바늘 사이의 간격을 구하여 

 

KMP 알고리즘을 응용하면 풀 수 있는 문제입니다.

 

우선, 시계 바늘 간의 간격을 구합니다.

 

예제 2번을 사용하면,

 

둘다 {90000, 270000}의 간격를 가졌습니다.

 

우리는 입력값을 통해 이 간격을 구해야 합니다.

 

1. 배열에 입력값을 모두 넣습니다. 

 

예시 : Arr = {0, 270000}

 

2. 배열의 마지막 값으로, 배열에서 가장 작은 값 + 360000을 넣습니다.

 

예시 : {0, 270000, 0 + 360000}

 

3. 배열 값 간의 모든 간격을 구하여 새로운 배열에 담습니다.

 

식 : Arr [index + 1] - Arr[index]

 

예시 : Interval = {270000, 90000}

 

 

자, 위와 같은 방식으로 2개의 Interval 배열을 구했다면, KMP 알고리즘을 활용합니다.

 

예를 들어, Interval 배열 2개가 다음과 같이 생성되었습니다.

 

Interval_A = {270000, 90000}

Interval_B = {90000, 270000}

 

우리는 예제 2번을 봤을 때, 답이 possible이라는 것을 알 수 있지만,

 

Interval 배열은 서로 순서가 다르게 나올 수 있기 때문에, 다음과 같이 수행해야 합니다.

 

우선, 한 쪽 Interval 배열의 크기를 2배로 하여 똑같은 값을 담겠습니다.

 

Interval_A = {270000, 90000, 270000, 9000}

Interval_B = {90000, 270000}

 

우리는 KMP 알고리즘을 이용해, Interval_B를 Interval_A와 비교하여 완전히 일치하는 순간이 생기면

 

"possible"을 출력하고, 그렇지 않으면 "impossible"을 출력하면 정답입니다.

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	scanf("%d", &N);
	
	//바늘 각도 입력
	int* clock_A = new int[N + 1];
	int* clock_B = new int[N + 1];
	for (int i = 0; i < N; i++) scanf("%d", &clock_A[i]);
	for (int i = 0; i < N; i++) scanf("%d", &clock_B[i]);
	clock_A[N] = 360000;
	clock_B[N] = 360000;
	sort(clock_A, clock_A + N + 1);
	sort(clock_B, clock_B + N + 1);
	
	clock_A[N] += clock_A[0];
	clock_B[N] += clock_B[0];
	//바늘간 각도 차이를 저장
	int* interval_A = new int[N];
	int* interval_B = new int[N];

	for (int i = 0; i < N; i++)
	{
		interval_A[i] = clock_A[i + 1] - clock_A[i];
		interval_B[i] = clock_B[i + 1] - clock_B[i];
	}
	delete[] clock_A;
	delete[] clock_B;

	//Pi 배열 생성
	int* Pi = new int[N];
	fill_n(Pi, N, 0);
	for (int left = 0, right = 1; right < N; right++)
	{
		while (0 < left && interval_A[left] != interval_B[right]) left = Pi[left - 1];
		if (interval_A[left] == interval_A[right]) Pi[right] = ++left;
	}

	//KMP 응용
	bool is_possible = false;
	for (int idx_A = 0, idx_B = 0; idx_B < 2 * N; idx_B++)
	{
		while (0 < idx_A && interval_A[idx_A] != interval_B[idx_B % N]) idx_A = Pi[idx_A - 1];
		if (interval_A[idx_A] == interval_B[idx_B % N]) idx_A++;
		if (idx_A == N)
		{
			is_possible = true;
			break;
		}
	}

	if (is_possible) printf("possible");
	else printf("impossible");

	delete[] Pi;
	delete[] interval_A;
	delete[] interval_B;
	return 0;
}

 

그 외

---