백준 10266 시계 사진들
23 Jun 2021https://www.acmicpc.net/problem/10266
n개의 동일한 시계 바늘의 위치가 찍힌 사진이 두 장 주어졌을 때 두 사진이 동일한 시각을 나타내는지 알아내는 문제이다. 시계에는 시계 바늘간의 위치만 구분할 수 있기 때문에 사진을 돌려서 일치하면 같은 시각을 나타내는 것이라 생각한다.
시계 바늘간의 위치가 중요한 것이기 때문에 바늘들간의 각도차를 중심으로 문제를 풀 것이다. 이 때 첫번째 바늘과 마지막 바늘간의 각도 역시 계산해줘야한다는 것을 명심하자.
예시로 4개의 바늘이 존재한다고 했을 때 각각의 사잇각을 ABCD라고 나타내보자. 그런데 두번재 사진은 각이 희한하게 주어져서 DABC 순으로 우리가 각도를 확인했다고 하자.
첫번째 사진의 각도 순서를 2번 이어붙여보자. 그러면 ABCDABCD가 될 것이고 이 안에는 ABCD, BCDA, CDAB, DABC 네 패턴이 모두 존재할 수 있게 된다. 이제 DABC에 해당했던 두번째 사진의 각도 순서가 ABCDABCD 속에 존재하는지 확인하면 두 사진은 동일한 시간이라 판별할 수 있다.
즉 두번째 사진의 각도 순서가 어떻게 나오든 첫번째 사진과 동일한 시간이라면 첫번째 각도순서를 두번 붙인 문자열 속에 해당 패턴이 등장하게 된다. 따라서 KMP알고리즘을 통해 이를 확인해주면 되는 문제이다.
- 전체 코드
func makepi(str: [Int]) -> [Int] {
var pi = Array(repeating: 0, count: str.count)
var j = 0
for i in 1..<str.count {
while j > 0 && str[i] != str[j] {
j = pi[j-1]
}
if str[i] == str[j] {
j += 1
pi[i] = j
}
}
return pi
}
func makeDiff(str: [Int]) -> [Int] {
var arr = [Int]()
for i in 0..<str.count-1 {
arr.append(str[i+1]-str[i])
}
arr.append(360000-str.last!+str[0])
return arr
}
let n = Int(readLine()!)!
let S = makeDiff(str: readLine()!.split(separator: " ").map{Int(String($0))!}.sorted())
let S1 = S + S
let S2 = makeDiff(str: readLine()!.split(separator: " ").map{Int(String($0))!}.sorted())
let pi = makepi(str: S2)
var i = 0
var j = 0
var result = false
while i+j < S1.count && i < S2.count {
let curr = i+j
while j > 0 && S1[curr] != S2[j] {
j = pi[j-1]
i = curr - j
}
if S1[curr] == S2[j] {
j += 1
if j == S2.count {
result = true
break
}
}
else {
i += 1
}
}
print(result ? "possible" : "impossible")