10266번: 시계 사진들

문제 출처 : https://www.acmicpc.net/problem/10266

10266번: 시계 사진들

언어 : Kotlin

 

문제 설명 :

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

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

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

 

입력 :

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

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

 

출력 :

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

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
6 1 2 3 4 5 6 7 6 5 4 3 1	impossible
2 0 270000 180000 270000	possible
7 140 130 110 120 125 100 105 235 205 215 220 225 200 240	impossible

 

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val size = 360000
    val n = readLine().toInt()
    val c1 = IntArray(size * 2)
    val c2 = IntArray(size)
    repeat(2) {
        val input = readLine().split(" ").map { it.toInt() }
        for (i in 0 until n) {
            when (it) {
                0 -> {
                    c1[input[i]] = 1
                    c1[size + input[i]] = 1
                }

                1 -> c2[input[i]] = 1
            }
        }
    }

    bw.write(kmp(c1, c2, size))
    bw.flush()
    bw.close()
}

fun kmp(c1: IntArray, c2: IntArray, size: Int): String {
    var index = 0
    val table = makeTable(c2, size)

    for (i in 0 until size * 2) {
        while (index > 0 && c1[i] != c2[index]) index = table[index - 1]
        if (c1[i] == c2[index]) {
            if (index == size - 1) {
                return "possible"
            } else {
                index++
            }
        }
    }

    return "impossible"
}

fun makeTable(c: IntArray, size: Int): IntArray {
    var index = 0
    val table = IntArray(size)

    for (i in 1 until size) {
        while (index > 0 && c[i] != c[index]) index = table[index - 1]
        if (c[i] == c[index]) table[i] = ++index
    }

    return table
}