[Kotlin] BOJ 16927 - 배열 돌리기 2

문제 소개

주어진 N×M 배열을 반시계 방향으로 R번 회전시킨 결과를 출력하는 문제다. 배열은 여러 겹의 “테두리(ring)”로 구성되어 있고, 각 ring을 독립적으로 회전시키면 된다.

---

접근 방법

1. 단순 시뮬레이션

처음엔 그냥 한 칸씩 R번 회전을 구현해보았다.
R이 작다면 문제없지만, 입력 제한을 보면 R ≤ 10^9.
→ 이렇게 하면 시간 초과가 발생한다.

---

2. 모듈러 연산으로 최적화

한 ring의 길이가 L일 때 R번 돌린 것은 사실상 R % L번 돌린 것과 같다.
예를 들어, 길이가 12인 ring을 1,000,000,007번 회전시키는 건 7번 회전과 동일하다.

이 아이디어로 “큰 R”을 줄여 시간 초과 문제는 해결할 수 있다.

---

3. 하지만 여전히 비효율적

여전히 R % L번 한 칸씩 이동을 해야 한다.
최악의 경우 여전히 시간이 오래 걸릴 수 있다.

---

4. 더 좋은 방법: 목적지 좌표 바로 계산

ring은 사실상 1차원 원형 배열이다.
따라서 ring의 좌표를 순서대로 나열한 뒤, 실제로는 한 번에 k = R % L만큼 이동한다고 볼 수 있다.

즉, i번째 좌표의 값은 원래 배열의 (i + k) % L번째 값이 된다.
이 방식이면 각 칸의 최종 위치를 바로 알 수 있고, 전체 복잡도는 O(N×M)으로 줄어든다.

ring의 구성 요소를 일직선으로 피는 부분은 아래 코드를 보고 이해

---

구현 (Kotlin)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.min

fun main() {
    BufferedReader(InputStreamReader(System.`in`)).use { br ->
        val (N, M, R) = br.readLine().split(" ").map { it.toInt() }
        val a = Array(N) { IntArray(M) }
        for (i in 0 until N) {
            val st = StringTokenizer(br.readLine())
            for (j in 0 until M) a[i][j] = st.nextToken().toInt()
        }

        val depth = min(N, M) / 2
        for (layer in 0 until depth) {
            val top = layer
            val left = layer
            val bottom = N - 1 - layer
            val right = M - 1 - layer

            val height = bottom - top
            val width  = right - left
            val L = 2 * (height + width)
            val k = R % L

            val rr = IntArray(L)
            val cc = IntArray(L)
            var p = 0

            for (c in left until right) { rr[p] = top; cc[p++] = c }
            for (r in top until bottom) { rr[p] = r; cc[p++] = right }
            for (c in right downTo left + 1) { rr[p] = bottom; cc[p++] = c }
            for (r in bottom downTo top + 1) { rr[p] = r; cc[p++] = left }

            val vals = IntArray(L) { idx -> a[rr[idx]][cc[idx]] } //핵심(링을 일직선으로 핌, 원형 큐 모양으로 생각하면 편하다)

            for (i in 0 until L) {
                a[rr[i]][cc[i]] = vals[(i + k) % L]
            }
        }

        val sb = StringBuilder()
        for (i in 0 until N) {
            for (j in 0 until M) {
                if (j > 0) sb.append(' ')
                sb.append(a[i][j])
            }
            sb.append('\n')
        }
        print(sb)
    }
}

---

정리

• 처음 접근: 단순 시뮬레이션 → R이 너무 커서 시간 초과
• 두 번째 접근: 모듈러 연산으로 R을 줄여 최적화 → 큰 R 문제 해결
• 세 번째 접근: ring을 1차원으로 보고, 각 칸의 최종 위치를 한 번에 계산 → O(N×M) 해결

이 문제의 핵심은 큰 R을 줄이는 발상과, 목적지 좌표를 바로 계산하는 최적화다.