[コートリン]白準12100号:2048-三星ソフトウェア能力試験出題

56869 ワード

三星寄付問題白駿コトリンテキストリンク

に答える

この問題の時間は5秒に制限されていますが、4方向に5回移動するだけなので、フルナビゲーション(逆トレース)が使用されます.

ついせき

上下左右に5回移動する角度から最高値を求めればよい.

fun permutation(cnt: Int) {
    if (cnt == 5) {
        board.forEach { array ->
            array.forEach { num ->
                answer = max(answer, num)
            }
        }
        return
    }

    val clone_board = Array(n) {IntArray(n)}
    for (i in board.indices) {
        clone_board[i] = board[i].clone()
    }
    for (i in 0..3) {
        move(i)
        permutation(cnt + 1)
        for (i in board.indices) {
            board[i] = clone_board[i].clone()
        }
    }
}

ブロックの移動

Blockを移動する際に指摘すべき部分があります
1回の移動では、マージされたブロックは別のブロックと再マージできません.
たとえば、次のゲーム版が存在するとします.
|2|2|2|
|2|2|2|
|4|4|4|
ここで1回上に移動すると、結果値は次のようになります.
|4|4|4|
|4|4|4|
|0|0|0|
したがって、스택とcursorという変数を使用して、ブロックが重複して結合できないことを保証するために方向に論理を記述します.

fun move(rotate: Int) {
    val clone_board = Array(n) { IntArray(n) }
    when (rotate) {
        0 -> {
            // 위 쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[i][c] = list[i]
                }
            }
        }
        1 -> {
            // 아래쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }

                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[board.size - 1 - i][c] = list[i]
                }
            }
        }
        2 -> {
            // 왼쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][i] = list[i]
                }
            }
        }
        3 -> {
            // 오른쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][board.size - 1 - i] = list[i]
                }
            }
        }
    }
    for (i in board.indices) {
        board[i] = clone_board[i].clone()
    }
}

Source Code

package 삼성SW역량테스트.`12100번_2048`

import java.util.*
import kotlin.math.max

lateinit var board: Array<IntArray>
var n: Int = 0
var answer = 0
fun main() {
    n = readln().toInt()
    board = Array(n) { IntArray(n) }

    for (i in board.indices) {
        val str = readln()
        board[i] = str.split(" ").map { it.toInt() }.toIntArray()
    }

    permutation(0)
    println(answer)

}
fun permutation(cnt: Int) {
    if (cnt == 5) {
        board.forEach { array ->
            array.forEach { num ->
                answer = max(answer, num)
            }
        }
        return
    }

    val clone_board = Array(n) {IntArray(n)}
    for (i in board.indices) {
        clone_board[i] = board[i].clone()
    }
    for (i in 0..3) {
        move(i)
        permutation(cnt + 1)
        for (i in board.indices) {
            board[i] = clone_board[i].clone()
        }
    }
}

fun move(rotate: Int) {
    val clone_board = Array(n) { IntArray(n) }
    when (rotate) {
        0 -> {
            // 위 쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[i][c] = list[i]
                }
            }
        }
        1 -> {
            // 아래쪽으로
            for (c in board[0].indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (r in board.size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }

                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[board.size - 1 - i][c] = list[i]
                }
            }
        }
        2 -> {
            // 왼쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].indices) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][i] = list[i]
                }
            }
        }
        3 -> {
            // 오른쪽으로
            for (r in board.indices) {
                val stack = Stack<Int>()
                var cursor = 0
                for (c in board[0].size - 1 downTo 0) {
                    if (board[r][c] == 0) continue
                    if (stack.isEmpty() || board[r][c] != stack.peek() || cursor != board[r][c]) {
                        stack.push(board[r][c])
                        cursor = board[r][c]
                    } else {
                        stack.push(stack.pop() * 2)
                        cursor = 0
                    }
                }
                val list = stack.toList()
                for (i in list.indices) {
                    clone_board[r][board.size - 1 - i] = list[i]
                }
            }
        }
    }
    for (i in board.indices) {
        board[i] = clone_board[i].clone()
    }
}

Reference

この問題について([コートリン]白準12100号:2048-三星ソフトウェア能力試験出題), 我々は、より多くの情報をここで見つけました https://velog.io/@blucky8649/코틀린-백준-12100번-2048-삼성-SW-역량-테스트-기출-문제-풀이

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

ケース-誤って削除されたテーブル

Djangoユニットテスト二三事