코틀린 코딩테스트 강좌, DDR을 해보자

이번 포스팅에서는 취업을 위한 알고리즘 문제 항목 중 하나로 자주 출제되는 ‘DDR’ 게임에 대한 문제를 다루어 보려고 합니다. 이 문제는 기본적인 배열 조작과 함께 알고리즘적 사고를 요하기 때문에, 코딩테스트 준비에 많은 도움이 될 것입니다. 문제의 정의와 해결 과정을 상세히 살펴보겠습니다.

문제 정의

당신은 ‘DDR(Dance Dance Revolution)’ 게임의 팬입니다. 이 게임에서는 스텝 패드에 직사각형 모양의 여러 방향(위, 아래, 왼쪽, 오른쪽)으로 화살표가 나타납니다. 스텝 패드는 N * N 크기의 격자판으로 구성되어 있습니다. 각 격자판의 위치에 화살표가 나타날 수 있으며, 특정 규칙에 따라 격자판을 스스로 채우고, 이를 기반으로 화살표를 윗 방향으로 압축해야 합니다.

주어진 DDR 스텝 패드의 초기 상태를 기반으로 압축된 상태를 반환하는 문제를 해결해야 합니다. 다음과 같은 규칙이 있습니다:

  • 게임 패드는 N * N 크기이며, 각 위치에는 0(비어 있음) 또는 1(화살표 있음)로 나타냅니다.
  • 모든 열에서 아래로 압축하여 나타나는 화살표를 반환해야 합니다. 즉, 열별로 아래로 밀어야 합니다.

입력 및 출력 형식

입력:

  1. 첫 번째 줄에는 스텝 패드의 크기 N(1 ≤ N ≤ 100)이 주어집니다.
  2. 다음 N줄에는 스텝 패드의 상태가 주어집니다. 각각은 0과 1로 이루어진 N개의 공백으로 구분된 숫자입니다.

출력:

압축된 스텝 패드의 상태를 N줄에 걸쳐 출력합니다. 각 줄은 0과 1로 구성되어 있으며, 공백으로 구분되어야 합니다.

예시

입력

    5
    0 0 0 0 0
    1 0 1 0 0
    1 1 0 1 0
    0 0 0 1 1
    0 0 0 0 0

출력

    0 0 0 0 0
    0 0 1 1 1
    1 1 1 0 0
    1 0 0 0 0
    1 0 0 0 0

문제 풀이 과정

이제 주어진 문제를 해결하기 위한 알고리즘을 계획해 보겠습니다. 이 문제는 주어진 격자판에서 열별로 아래로 압축하는 과정을 구현해야 합니다. 단계적으로 접근해 보겠습니다.

1단계: 데이터 구조 선택

각 입력을 워크스페이스에 저장할 이중 배열(2차원 배열)을 사용합니다. 각 씬을 확인하여 1의 개수만 세기 위해 각 열에 대한 리스트를 생성하겠습니다.

2단계: 압축 로직 구현

각 열을 개별적으로 확인해서 1의 개수를 세고, 최종적으로 구조를 아래로 맞추는 방식으로 압축을 수행합니다. 이를 위해 새롭게 구성된 배열에 하단부터 1을 배치하고, 나머지는 0으로 채우는 방식으로 접근합니다.

3단계: 코틀린 코드 작성

이제 코틀린 언어로 위 과정을 구현해보겠습니다. 다음은 구현된 코드입니다:

    fun compressDDRPads(n: Int, pads: Array): Array {
        // 결과를 저장할 이중 배열 초기화
        val result = Array(n) { IntArray(n) }

        // 각 열을 순회하여 아래로 압축
        for (j in 0 until n) {
            var count = 0

            // 열을 돌며 1의 개수 세기
            for (i in 0 until n) {
                if (pads[i][j] == 1) {
                    count++
                }
            }

            // 압축된 결과를 아래부터 채우기
            for (i in n - 1 downTo n - count) {
                result[i][j] = 1
            }
        }

        return result
    }

    // 예시 입력
    fun main() {
        val n = 5
        val pads = arrayOf(
            intArrayOf(0, 0, 0, 0, 0),
            intArrayOf(1, 0, 1, 0, 0),
            intArrayOf(1, 1, 0, 1, 0),
            intArrayOf(0, 0, 0, 1, 1),
            intArrayOf(0, 0, 0, 0, 0)
        )

        val compressedPads = compressDDRPads(n, pads)

        // 결과 출력
        for (row in compressedPads) {
            println(row.joinToString(" "))
        }
    }

결론

이번 포스팅에서는 DDR 문제를 코틀린을 사용하여 해결하는 과정을 살펴보았습니다. 문제 해결 과정에서 알고리즘적 사고와 데이터 구조에 대한 이해가 중요하다는 것을 알 수 있습니다. 실제 코딩테스트에서 반복적으로 연습함으로써 이러한 문제를 쉽게 해결할 수 있을 것입니다. 앞으로도 다양한 알고리즘 문제를 통해 코딩 실력을 더욱 심화시키길 바랍니다.

참고 자료