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

문제 풀이 아이디어

처음에 문제를 보았을 때는 이차원 배열을 사용하지 않고 할 수 있는 방법도 있지 않을까 생각을 했습니다만, 삼각 달팽이를 직접 구현하지 않고 푸는 것은 불가능합니다. 따라서 이차원 배열로 삼각 달팽이를 직접 구현한 이후이 이를 1차원 배열로 바꾸어 주어야 합니다.

삼각 달팽이를 구현할 때 다음 숫자를 쓰는 방향은 아래, 오른쪽, 위 3가지 입니다. 각 방향으로 진행하다가 다음 위치가 막히면 (삼각형의 끝에 도달하거나, 다른 숫자가 있는 경우) 방향을 전환하면 됩니다.

저 같은 경우는 방향을 전환하는 타이밍을 다음 위치에 다른 숫자가 이미 있는지 or 삼각형 밖으로 벗어났는지를 보고 결정했습니다만, 다른 분들의 풀이를 참고하니 삼각 달팽이의 변의 길이가 방향을 전환할 때마다 1씩 줄어든다는 점에서 착안해서 더 간단한 코드를 짜셨더라구요. 예를 들면 n이 4인 경우 처음에 아래 방향으로는 4개의 숫자를 쓴 이후에 오른쪽으로 방향 전환해서 3개의 숫자를 씁니다. 그리고 위로 방향을 전환해서 2개의 숫자를, 마지막으로 다시 아래로 방향을 전환해서 1개의 숫자를 쓰게 됩니다. (4 → 3 → 2 → 1)

두 방식을 모두 소개해보도록 하겠습니다.

코드

😅 다음 위치를 보고 방향 전환

// 진행 방향
enum Direction {
    case down, right, up
}

func solution(_ n:Int) -> [Int] {
    // 이차원 배열
    var matrix = Array(repeating: Array(repeating: 0, count: n), count: n)
    
    // 첫 방향은 down 이므로 -1, 0에서 시작
    var i = -1
    var j = 0
    var num = 1
    var direction = Direction.down

    // num의 최대 크기는 1 + 2 + ... + n
    while num <= n * (n + 1) / 2 {
        switch direction {
        // 진행 방향이 아래인 경우
        case .down:
            // 아래로 한칸 내려갔을 때 삼각형 밖으로 벗어나지 않고, 이미 다른 숫자가 있지는 않는지 확인
            if i + 1 < n && matrix[i + 1][j] == 0 {
                i += 1 //👉 아래로 1칸
                matrix[i][j] = num //👉 숫자 쓰고
                num += 1 //👉 숫자 + 1
            // 위 조건을 만족 못하면 방향 전환
            } else {
                direction = .right
            }
        // 진행 방향이 오른쪽인 경우
        case .right:
            // 오른쪽으로 한칸 갔을 때 삼각형 밖으로 벗어나지 않고, 이미 다른 숫자가 있지는 않는지 확인
            if j + 1 < n && matrix[i][j + 1] == 0 {
                j += 1 //👉 오른쪽으로 한칸
                matrix[i][j] = num //👉 숫자 쓰고
                num += 1 //👉 숫자 + 1
            // 위 조건을 만족 못하면 방향 전환
            } else {
                direction = .up
            }
        // 진행 방향이 위쪽인 경우
        case .up:
            // 위로 한칸 (삼각형이므로 왼쪽으로도 한칸) 갔을 때 삼각형 밖으로 벗어나지 않고, 이미 다른 숫자가 있지는 않는지 확인
            if i - 1 >= 0 && j - 1 >= 0 && matrix[i - 1][j - 1] == 0 {
                i -= 1 //👉 위로 한칸
                j -= 1 //👉 왼쪽으로 한칸
                matrix[i][j] = num //👉 숫자 쓰고
                num += 1 //👉 숫자 + 1
            // 위 조건을 만족하지 못하면 방향 전환
            } else {
                direction = .down
            }
        }
    }
    
    // 정답 배열
    var ans = [Int]()
    
    // 0은 제거하고 정답 배열에 이차원 배열의 1줄씩 추가
    for line in matrix {
        ans += line.filter { $0 != 0 }
    }
    
    return ans
}

변의 길이를 1씩 줄여가면서 방향 전환

func solution(_ n:Int) -> [Int] {
    var array = Array(repeating: Array(repeating: 0, count: n), count: n)
    var i = -1
    var j = 0
    var num = 1
    
    // 총 n번의 방향 전환
    for k in 0..<n {
        // 방향 전환할 때마다 길이는 1씩 줄어들음
        for _ in 0..<(n - k) {
            // 방향 (아래 -> 오른쪽 -> 위)를 순환하므로 k를 기준으로 3으로 나눈 나머지를 사용하면 된다.
            if k % 3 == 0 {
                i += 1 //👉 아래
            } else if k % 3 == 1 {
                j += 1 //👉 오른쪽
            } else {
                i -= 1
                j -= 1 //👉 위
            }
            array[i][j] = num
            num += 1
        }
    }
    
		// array를 합치기 위해서 reduce 사용
    return array.reduce([], { $0 + $1.filter { $0 != 0 } })
}