[프로그래머스][Kotlin] 정수를 나선형으로 배치하기

목차

문제 정보

https://school.programmers.co.kr/learn/courses/30/lessons/181832

프로그래머스

난이도 : 0 ~ 1

유형 : 그래프 탐색, 구현

시간 :  O(n^2)

 

---

문제 풀이

처음 접해보는 유형이면 어려울 수 있지만 방향을 바꾸는 아이디어만 알고 있으면 쉽게 풀 수 있는 문제라고 생각한다.(그래서 0레벨인가?.)

(SW Expert Academy에도 매우 유사한 문제 있다.)

 

(0, 0)에서 시작하여 오른쪽 -> 아래 -> 왼쪽 -> 위   방향으로 모든 숫자를 다 채울 때까지 계속해서 순환하는 구조이다.

 

숫자를 배치하는 방식으로 일단 한 방향으로 숫자를 배치할 수 있을 때까지 전진하며 배치하고

만약 다음 칸이 좌표를 벗어나거나 혹은 다음 칸에 이미 숫자가 배치되어 있으면 방향을 바꾸면 된다.

 

방향을 바꾸는 아이디어는 현재까지 방향을 바꾼 횟수를 카운트하여

방향을 바꿔야 할 때 (현재까지 방향을 바꾼 횟수 % 4) 연산을 해주면 된다.

ex )

[오른쪽 방향 값] = 0

[아래 방향 값] = 1

[왼쪽 방향 값] = 2

[위 방향 값] = 3

 

오른쪽으로 이동 -> 변경 횟수 '0'

아래로 변경 -> 변경 횟수'1'

왼쪽으로 변경 -> 변경 횟수 '2'

위로 변경 -> 변경 횟수'3'

다시 오른쪽으로 변경 -> 변경 횟수 '4'이지만  (현재까지 방향을 바꾼 횟수 % 4) 연산을 하면 다시 '0'이 되므로 오른쪽 방향 값으로 변하게 된다.

 

---

코드

class Solution {
    val dir = arrayOf(
        arrayOf(0, 1, 0, -1),
        arrayOf(1, 0, -1, 0)
    )

    fun solution(n: Int): Array<IntArray> {
        var answer: Array<IntArray> = arrayOf()

        for (i in 0 until n) {
            answer += IntArray(n)
        }

        var cnt = 1;
        var dirIdx = 0;
        var x = 0
        var y = 0
        while (cnt <= n * n) {
            while (!(x < 0 || x >= n || y < 0 || y >= n) && answer[x][y] == 0) {
                answer[x][y] = cnt++
                x += dir[0][dirIdx]
                y += dir[1][dirIdx]
            }

            x -= dir[0][dirIdx]
            y -= dir[1][dirIdx]

            dirIdx++
            if (dirIdx % 4 == 0) {
                dirIdx = 0
            }

            x += dir[0][dirIdx]
            y += dir[1][dirIdx]
        }
        return answer
    }
}