<프로그래머스> 삼각 달팽이(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EC%82%BC%EA%B0%81%20%EB%8B%AC%ED%8C%BD%EC%9D%B4

[프로그래머스]

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

 

이 문제를 보고는 내가 풀 수 있을까 싶은 생각이 먼저 들었다.

미리 겁먹는 느낌...?

그런데 생각보다 방법이 금방 떠올랐고 그 방법은 문제 해결로 이어졌다.

 

내가 생각한 방법은 각 방향을 대한 Boolean 값을 두고 조건에 따라서 방향을 바꾸도록 한 것이다.

반복문 한번으로 코드가 마무리된다.

 

물론 처음에는 실패가 떴다.

정확히는 시간초과다.

시간복잡도도 O(N)인 거 같고 사용하는 공간도 작은 거 같은데 왜 걸릴까... 고민이 시작되었다.

그 해결은 생각보다 단순하고 이해가 되지 않았다.

나는 삼각형 배열을 2차원 배열로 구성했는데 처음에는 길이가 다른 IntArray를 1개의 row로 넣었다.

정말 삼각형처럼 말이다.

그거를 그냥 주어지는 입력값에 맞는 정사각형 2차원 배열로 만드니까 통과했다.

통과했다...?!

 

이 부분은 좀 이유를 알아봐야겠다.

좀 질문해보고 생각해본 걸로는 O(N^2)이 넘으면 안 된다는 건 확실한 케이스라고 들었기 때문에 반복문 안에서 += 연산자를 써서 그런게 아닐까 싶다.

이전에도 이렇게 += 연산자로 해서 시간초과가 난 경우가 있었던 거 같은데 그 때 포스팅해놓은 걸 떠올려보면 배열의 끝에 하나의 요소를 추가한 새로운 배열을 생성한다고 했었다.

그걸 생성하는 과정이 O(N^2)을 만들며 시간초과가 나지 않았을까...

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    fun solution(n: Int): IntArray {
        var answer: IntArray = intArrayOf()
        // 삼각형 배열
        var triangle = Array(n) {IntArray(n) {0} }
        // 방문 체크용 배열
        var visited = Array(n) {BooleanArray(n) {false} }

        // 총 필요한 숫자
        val totalNum = n * (n + 1) / 2
        // 현재 숫자
        var curNum = 1
        // 현재 좌표
        var row = 0
        var col = 0
        // 위쪽에서 왼쪽아래로 가는 방향
        var isLeft = true
        // 왼쪽에서 오른쪽으로 가는 방향
        var isBottom = false
        // 아래쪽에서 왼쪽위로 가는 방향
        var isRight = false

        while (true) {
            triangle[row][col] = curNum
            visited[row][col] = true
            
            // 방향 체크 후 좌표 변경
            when {
                isLeft -> {
                    if (triangle.size == row + 1 || visited[row + 1][col]) {
                        isLeft = false
                        isBottom = true
                        col++
                    } else {
                        row++
                    }
                }
                isBottom -> {
                    if (row == col || visited[row][col + 1]) {
                        isBottom = false
                        isRight = true
                        row--
                        col--
                    } else {
                        col++
                    }
                }
                isRight -> {
                    if (visited[row - 1][col - 1]) {
                        isRight = false
                        isLeft = true
                        row++
                    } else {
                        row--
                        col--
                    }
                }
            }
            
            // 삼각형을 다 채웠으면 탈출
            if (curNum == totalNum) break
            curNum++
        }

        // 필요한 값들을 뽑아서 answer에 저장
        triangle.forEach {
            answer += it.filter { num -> num != 0 }
        }
        
        return answer
    }
}