10266번
22.03.08
문제
상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바늘들의 위치만 구분 할 수 있습니다.
우리의 상근이는 두 사진의 시계가 같은 시각을 나타낼 수 있는지 궁금해져 각 사진을 서로 다른 각도로 돌려보려고 합니다.
두 사진에 대한 묘사가 주어질 때, 두 사진의 시계가 같은 시각을 나타내는지 결정하세요.
입력
첫 줄에는 바늘의 수를 나타내는 정수 n(2 ≤ n ≤ 200 000)이 주어진다.
다음 두 줄에는 각각 n개의 정수가 주어지며, 주어지는 정수 ai(0 ≤ ai < 360,000)는 각 사진에서 바늘의 시계 방향 각도를 나타낸다. 이때 바늘의 각도는 특정 순서대로 주어지지는 않는다. 한 줄에는 같은 각도값이 두 번 이상 주어지지 않는다. 즉, 한 시계 안의 모든 각도값은 서로 구분된다.
출력
두 시계 사진이 같은 시각을 나타내고 있다면 "possible"을 아니면 "impossible"을 출력하시오.
int 배열로 풀이하려 했지만, 여러 풀이를 참조한 결과 KMP 매칭 알고리즘을 이용해 각도 값을 배열에 입력하는 것이 아닌
각 바늘이 가질 수 있는 각도 값 0<=k<36000 크기의 배열에 바늘이 존재하는 각도에 1, 존재하지 않는 각도에 0을 입력하는 방식을 이용하는 것을 확인했다. 그리고 표본이 될 1번째 시계의 배열을 2배로 복사하여 확장해 순환하여 비교하기 용이하도록 한다.
그리고 1번째 시계를 탐색하여 일치 여부가 확인되면 possible을 출력, 모두 탐색 완료 후 일치 여부가 확인되지않으면 impossible을 출력하도록 한다.
Reference
https://loosie.tistory.com/578
