[KOTLIN] 삼각 달팽이

- https://programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• n은 1 이상 1,000 이하입니다.

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

풀이

1. 주어진 삼각형을 왼쪽으로 붙여서 직각 삼각형으로 생각한다.

2. 위의 그림과 같이 (위쪽 -> 아래쪽), (왼쪽 -> 오른쪽), (대각선) 이동을 하면서 숫자를 채워 나간다.

3. top = 1, bottom = n, left = 1, right = n 로 설정한다.

4. 초기 value 를 0으로 설정하고 max(다 채웠을 때 마지막 숫자) 와 비교하여 커질때 까지 반복한다.

전체 코드

class Solution {
    fun solution(n: Int): IntArray {
        val answer = mutableListOf<Int>()

        // 삼각형을 왼쪽으로 밀어서 직각 삼각형으로 생각한다.
        /** n = 4 일 경우
         * 1(1,1)
         * 2(2,1) 9(2,2)
         * 3(3,1) 10(3,2) 8(3,3)
         * 4(4,1) 5 (4,2) 6(4,3) 7(4,4)
         **/
        val matrix = Array(n + 1) {
            IntArray(n + 1) {
                0
            }
        }
        var value = 1
        val max = n * (n + 1) / 2
        var top = 1
        var bottom = n
        var left = 1
        var right = n

        while (value <= max) {
            // 위에서 아래로 숫자를 채운다.
            for (i in top..bottom) {
                if (value > max) break
                matrix[i][left] = value++
                //println("top=>bottom matrix[$i][$left] ${matrix[i][left]}")
            }

            left++
            top++

            // 왼쪽에서 오른쪽으로 숫자를 채운다.
            for (i in left..right) {
                if (value > max) break
                matrix[bottom][i] = value++
                //println("left=>right matrix[$bottom][$i] ${matrix[bottom][i]}")
            }

            bottom--
            right--

            // 대각선으로 숫자를 채운다.
            for (i in bottom downTo top) {
                if (value > max) break
                matrix[i][i - (bottom - right)] = value++
                //println("diagonal matrix[$i][${i - (bottom - right)}] ${matrix[i][i - (bottom - right)]}")
            }

            top++
            right--
        }


        for (i in 1..n) {
            for (j in 1..n) {
                if (matrix[i][j] !=0 ) {
                    //println("result : ${matrix[i][j]}")
                    answer.add(matrix[i][j])
                }
            }
        }

        return answer.toIntArray()
    }
}