[Programmers] 삼각 달팽이 (Level 2)

문제

링크

문제 요약

달팽이가 지나간 길

달팽이가 높이 n인 삼각형을 지나간다. 지나가는 길은

왼쪽 아래 대각선으로 -> 오른쪽 직선으로 -> 왼쪽 위 대각선으로 삼각형의 한 바퀴를 돈다.

달팽이가 지나간 길을 배열로 반환해야 한다. 

 

풀이

가장 처음 든 생각은 저 삼각형을 어떤 자료구조로 나타내야 할까였다.

삼각형을 왼쪽으로 미뤄본다면 이차원배열이 되서 그려보면 아래와 같다.

n=4일 때 2차배열

이차배열로 표현하면,

[[1], [2,9], [3,10,8], [4,5,6,7]] 이다.

안쪽 배열은 배열의 수가 1개씩 증가한다.

 

n=4일 때 달팽이가 지나간 길

그럼 이 그림에서 달팽이가 지나간 길을 생각해보자.

달팽이가 지나간 길은 파란색 길이다.

이 길들을 index로 표현하면 아래와 같다.

(0,0), (1,0), (2,0), (3,0) 

(3,1), (3,2), (3,3)

(2,2), (1,1)

(2,1)

 

써내려가다보니 규칙이 보인다.

row와 column으로 나눠서 생각해보면,

1. column 1씩 증가

2. row 1씩 증가

3. column, row 1씩 감소 

4. 1~3을 몇 번 반복한다. 

 

여기서 몇 번 반복해야하는 지 구하기 위해, n=5인 경우를 한번 더 써보았다.

 

i=0:

   (0,0) (1,0) (2,0) (3,0) (4,0)

   (4,1) (4,2) (4,3) (4,4)

   (3,3) (2,2) (1,1) 

i=1:

   (2,1) (3,1)

   (3,2)

끝

 

n=4일때나 n=5일 때나 달팽이가 한번 돌 때, 삼각형의 변 하나가 사라진다. 

루프의 시작을 n으로 한다면 3씩 줄여나가며 0이하라면 빠져나오면 된다. (for문으로 구현)

 

풀이 

import Foundation

func solution(_ n:Int) -> [Int] {
    var triangle: [[Int]] = []
    
    // ✅ 삼각형 만들기 
    for i in 0..<n {
        let temp : [Int] = Array.init(repeating: 0, count: i+1)
        triangle.append(temp)
    }

    var column: Int = -1
    var row: Int = 0
    var count: Int = 0
    for i in stride(from: n, to: 0, by: -3) {
        for _ in 0..<i {
            count += 1
            column += 1
            triangle[column][row] = count
        }
        
        // ✅ 0..<i-1 범위 체크
        guard 0 <= i-1 else { continue }

        for _ in 0..<i-1 {
            count += 1
            row += 1
            triangle[column][row] = count
        }
        
        // ✅ 0..<i-2 범위 체크
        guard 0 <= i-2 else { continue }

        for _ in 0..<i-2 {
            count += 1
            column -= 1
            row -= 1
            triangle[column][row] = count
        }
    }

    return triangle.flatMap { $0 }
}

 

---

배운 점 

1. Stride를 까먹고 있었다..

Stride(from: to: by:) - index가 from..<to 범위에서 by만큼 이동

 

2. flatMap 다시 복기 💪🏻

SementOfResult의 각 요소를 transform을 호출한 결과를 포함하는 배열을 반환한다.

collection이나 sequence의 각 요소마다 sequence가 생기는 경우 flat해주기 위해 사용한다. 

O(m+n) (n: sequence의 길이, m: 결과의 길이)

func flatMap<SegmentOfResult>(_ transform: (Self.Element) throws -> SegmentOfResult) rethrows -> [SegmentOfResult.Element] where SegmentOfResult : Sequence