이번 포스팅에서는 취업을 위한 알고리즘 문제 항목 중 하나로 자주 출제되는 ‘DDR’ 게임에 대한 문제를 다루어 보려고 합니다. 이 문제는 기본적인 배열 조작과 함께 알고리즘적 사고를 요하기 때문에, 코딩테스트 준비에 많은 도움이 될 것입니다. 문제의 정의와 해결 과정을 상세히 살펴보겠습니다.
문제 정의
당신은 ‘DDR(Dance Dance Revolution)’ 게임의 팬입니다. 이 게임에서는 스텝 패드에 직사각형 모양의 여러 방향(위, 아래, 왼쪽, 오른쪽)으로 화살표가 나타납니다. 스텝 패드는 N * N 크기의 격자판으로 구성되어 있습니다. 각 격자판의 위치에 화살표가 나타날 수 있으며, 특정 규칙에 따라 격자판을 스스로 채우고, 이를 기반으로 화살표를 윗 방향으로 압축해야 합니다.
주어진 DDR 스텝 패드의 초기 상태를 기반으로 압축된 상태를 반환하는 문제를 해결해야 합니다. 다음과 같은 규칙이 있습니다:
- 게임 패드는 N * N 크기이며, 각 위치에는 0(비어 있음) 또는 1(화살표 있음)로 나타냅니다.
- 모든 열에서 아래로 압축하여 나타나는 화살표를 반환해야 합니다. 즉, 열별로 아래로 밀어야 합니다.
입력 및 출력 형식
입력:
- 첫 번째 줄에는 스텝 패드의 크기 N(1 ≤ N ≤ 100)이 주어집니다.
- 다음 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 문제를 코틀린을 사용하여 해결하는 과정을 살펴보았습니다. 문제 해결 과정에서 알고리즘적 사고와 데이터 구조에 대한 이해가 중요하다는 것을 알 수 있습니다. 실제 코딩테스트에서 반복적으로 연습함으로써 이러한 문제를 쉽게 해결할 수 있을 것입니다. 앞으로도 다양한 알고리즘 문제를 통해 코딩 실력을 더욱 심화시키길 바랍니다.
참고 자료
- 코틀린 공식 문서
- GeeksforGeeks – 알고리즘 및 자료 구조
- HackerRank – 코딩 문제 연습