백준 - 17822 원판 돌리기 (코틀린)

[문제]

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

[풀이]

시뮬레이션과 구현 문제로 주어진 문제에 맞게 코드를 작성하면 된다. 처음 간단한 문제라고 생각했던 것에 비해 오래 시간이 끌린 부분이 있었는데 회전을 하는 부분에서 시간이 걸렸다. 한 칸 씩 움직일 때는 임시 변수 하나를 두어 인덱스가 0보다 작거나 배열 크기보다 클 때에 그에 맞게 회전이 가능했으나 두 칸 이상씩 움직일 땐 범위를 벗어난 수들을 따로 저장을 해야했고 이 때 Deque를 이용했다. Deque를 이용하여 시계 방향과 반시계 방향에 따라 stack처럼 last를 뺄지 queue처럼 first를 뺄지 정하였고 범위안의 수들은 일반 대입으로, 범위 밖의 수는 deque를 이용하여 회전을 하였다. 이후 인접한 수끼리 비교를 하는데 0이 아니라는 조건이 필요했고, queue에 저장을 했다. queue가 비어 있지 않으면 이 수들을 빼서 0으로 바꾸었고 큐가 비어 있다면 평균을 구해 평균보다 클 땐 += 1 연산 작을 땐 -= 1 연산을 해주었다. 모든 수가 0인 경우에도 큐가 비어있기 때문에 0이 아닌 숫자의 개수가 0일 땐 따로 계산하지 않고 넘어가는 처리가 필요하다.

[코드]

import java.util.*

private var n = 0
private var m = 0
private var t = 0
private lateinit var arr : Array<IntArray>
private lateinit var rotateArr : Array<IntArray>
private var sum = 0
private var cnt = 0
fun main() {
    val br = System.`in`.bufferedReader()
    br.readLine().split(" ").map { it.toInt() }.apply {
        n = this[0]
        m = this[1]
        t = this[2]
    }
    arr = Array(n){ IntArray(m) }
    repeat(n){
        arr[it] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
        arr[it].forEach { n ->
            sum += n
        }
    }
    rotateArr = Array(t){ IntArray(3) }
    cnt = n * m
    repeat(t){
        val (x,d,k) =  br.readLine().split(" ").map { it.toInt() }.toIntArray()
        rotate(x,d,k)
    }
    println(sum)

}

private fun rotate(x : Int, d : Int, k : Int){
    val queue : Queue<Pair<Int,Int>> = ArrayDeque()
    val deque : Deque<Int> = ArrayDeque()
    if(d == 0){ // 시계
        for(i in x .. n step x) {
            for(j in m-1 downTo 0){
                if(j+k>=m){
                    deque.add(arr[i-1][j])
                }
                else {
                    arr[i-1][j+k] = arr[i-1][j]
                }
            }
            if(deque.isNotEmpty()){
                for(j in 0 until k){
                    arr[i-1][j] = deque.pollLast()
                }
            }
        }
    }
    else {
        for(i in x .. n step x){
            for(j in 0 until m){
                if(j-k<0){
                    deque.add(arr[i-1][j])
                }
                else {
                    arr[i-1][j-k] = arr[i-1][j]
                }
            }
            if(deque.isNotEmpty()){
                for(j in m-k until m){
                        arr[i-1][j] = deque.poll()
                }
            }
        }
    }
    for(i in 0 until n){
        for(j in 0 until m - 1){
            if(arr[i][j+1]!= 0 && arr[i][j] != 0 &&arr[i][j] == arr[i][j+1]) {
                queue.add(Pair(i, j))
                queue.add(Pair(i, j+1))
            }
        }
        if(arr[i][m-1]!= 0 && arr[i][0] != 0 &&arr[i][m-1]== arr[i][0]) {
            queue.add(Pair(i, m - 1))
            queue.add(Pair(i, 0))
        }
    }
    for(i in 1 until n){
        for(j in 0 until m){
            if(arr[i-1][j]!= 0 && arr[i][j] != 0 && arr[i-1][j]== arr[i][j] ){
                queue.add(Pair(i-1, j))
                queue.add(Pair(i, j))
            }
            if(i+1 >= n) continue
            if(arr[i+1][j]!= 0 && arr[i][j] != 0 &&arr[i][j]==arr[i+1][j]){
                queue.add(Pair(i+1, j))
                queue.add(Pair(i, j))
            }
        }
    }
    if(queue.isNotEmpty()) {
        while (queue.isNotEmpty()) {
            val (x, y) = queue.poll()
            if(arr[x][y] != 0) {
                sum -= arr[x][y]
                cnt -= 1
            }
            arr[x][y] = 0
        }
    }
    else {
        if (cnt != 0) {
            val avg = sum / cnt
            val bool = (sum % cnt == 0) // true면 정수
            var newSum = sum
            for (i in 0 until n) {
                for (j in 0 until m) {
                    if (arr[i][j] != 0) {
                        if (!bool) {
                            if (arr[i][j] <= avg) {
                                arr[i][j] += 1
                                newSum += 1
                            } else {
                                arr[i][j] -= 1
                                newSum -= 1
                            }
                        } else {
                            if (arr[i][j] < avg) {
                                arr[i][j] += 1
                                newSum += 1
                            } else if (arr[i][j] > avg) {
                                arr[i][j] -= 1
                                newSum -= 1
                            }
                        }
                    }
                }
            }
            sum = newSum
        }
    }
}