[Swift] [25일차] 삼각달팽이

programmers-삼각달팽이

투박하게 그림을 그려봤는데, 다음과 같이 계속 삼각형이 시작되는 구조다. 이걸 2차원배열로 잘 기록해둔다음에 평탄화 작업을 해주면 답이 나올 것 같았다.

---

문제 풀이 과정

1. 왼쪽부터 아래로 쭉 !
2. 맨 아래서 오른쪽으로 쭉 !
3. 맨아래서 위로 쭉 !
   이렇게 3가지를 수행할 수 있게 했고, 사진처럼 나와있듯이
   이거 3개를 수행할 수 있으면 시작위치와 크기만 다른 삼각형 형태가 중첩되어있는 구조라고 생각했다.(껍질처럼)

삼각형 함수

 var current_cnt = 1 // 칸 안의 숫자값 (1씩 증가)
    var snail = (0 ..< n).map { Array(repeating: 0, count: $0 + 1) }

    func triangle(_ start: (Int, Int), _ numOfTriangle: Int) {
        for i in start.0 ..< n - numOfTriangle { // 맨왼쪽행에서 쭉 내려오기
            snail[i][start.1] = current_cnt
            current_cnt += 1
            if i == n - numOfTriangle - 1 {
                current_cnt -= 1
            }
        }

        for lastRowIdx in numOfTriangle ... n - (2 * numOfTriangle) - 1 { // 맨 아래서 오른쪽으로 쭉
            snail[n - numOfTriangle - 1][lastRowIdx] = current_cnt
            current_cnt += 1
        }
        for bottomUpIdx in (start.0 + 1 ..< (n - numOfTriangle)).reversed() { // 아래서 올라오기
            if bottomUpIdx == n - numOfTriangle - 1 {
                current_cnt -= 1
            }
            snail[bottomUpIdx][bottomUpIdx - numOfTriangle] = current_cnt // 층별로 다름
            current_cnt += 1
        }
    }

for문 한개랑 하나의 로직이다. (계속 index Error가 나서 이부분을 조율하는데에만 1시간을 넘게 쓴거같다. 풀릴 것 같다보니 이걸 놓아주기도 힘들어서..)

중간에 current -= 1 이 있는 이유는 중복될때 맨아래까지 뚫고, 그아래서도 왼쪽부터 시작하니까 겹치는 부분에 대해서는 한번만 + 될 수 있게 한 번씩 끝점에서 -1을 수행했다.

여기까지는 그대로 인덱스 에러 고치면서 어떻게어떻게 풀었는데,

시작점에 따라 삼각형 형태로 숫자를 적어나가고 있어서,, 이게 일련된 규칙이 있을텐데 예를들어

n=3,4,5,6 일때는 삼각형이 형태가 2개다 (0,0) , (2,1) 시작 삼각형
n = 7 일때는 형태가 3개 (0,0) , (2,1) , (4 , 2)
이 규칙을 어떻게 발견하지? 에서 또 시간을 오래 썼다.

초기코드

var count = 0
for i in 0 ...  where i % 2 == 0 {
	triangle((i,i/2) , count )
    count += 1
}

이런식으로 2씩 늘어나는 등차수열로 해주려고했는데 , 6이 계속 (4,2) 를 갖게돼서 이부분 조율을 엄청 신경 썼던 것 같다. 결국에는 삼각형이니까 세변을 가지니까 전체삼각형의 크기 n에서 3으로 나눠주는데, 이제 6과 7의 차등을 둬야하니 이를 ceil로 차등을 줬다. 그래야 6은 2가되고, 7은 3이된다 !

수정안

let numTriangles = Int(ceil(Double(n) / 3.0))

    for count in 0 ..< numTriangles {
        let start = (count * 2, count) // 시작점 계산
        triangle(start, count)
    }

---

이제 마지막으로 2차원 배열을 1차원 배열로 바꾸기!

평탄화 작업이라고 하는 것 같은데, 이것도 수정을 거쳐서 더 효율적으로 바꿔줬다.

평탄화 초기코드

let a = [[1], [2, 9], [3, 10, 8], [4, 5, 6, 7]]
var stack = [Int]()
for element in a {
    for e in element {
        stack.append(e)
    }
}
print(stack) // [1,2,9,3,8,4,5,6,7]

flatMap 사용코드

let a = [[1], [2, 9], [3, 10, 8], [4, 5, 6, 7]]
let stack = a.flatMap { $0 }
print(stack) // [1,2,9,3,8,4,5,6,7]

---

완성코드

import Foundation

func solution(_ n: Int) -> [Int] {
    var current_cnt = 1 // 칸 안의 숫자값 (1씩 증가)
    var snail = (0 ..< n).map { Array(repeating: 0, count: $0 + 1) }

    func triangle(_ start: (Int, Int), _ numOfTriangle: Int) {
        for i in start.0 ..< n - numOfTriangle { // 맨왼쪽행에서 쭉 내려오기
            snail[i][start.1] = current_cnt
            current_cnt += 1
            if i == n - numOfTriangle - 1 {
                current_cnt -= 1
            }
        }

        for lastRowIdx in numOfTriangle ... n - (2 * numOfTriangle) - 1 { // 맨 아래서 오른쪽으로 쭉
            snail[n - numOfTriangle - 1][lastRowIdx] = current_cnt
            current_cnt += 1
        }
        for bottomUpIdx in (start.0 + 1 ..< (n - numOfTriangle)).reversed() { // 아래서 올라오기
            if bottomUpIdx == n - numOfTriangle - 1 {
                current_cnt -= 1
            }
            snail[bottomUpIdx][bottomUpIdx - numOfTriangle] = current_cnt // 층별로 다름
            current_cnt += 1
        }
    }
    let numTriangles = Int(ceil(Double(n) / 3.0))

    for count in 0 ..< numTriangles {
        let start = (count * 2, count) // 시작점 계산
        triangle(start, count)
    }

    return snail.flatMap { $0 }
}

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

---

타인의 코드

import Foundation

func solution(_ n:Int) -> [Int] {
    var answer = Array(repeating: 0, count: (n + 1) * n / 2)    // 가우스 공식을 사용해서 최종 배열의 크기를 계산

    var number = 1      // 1부터 차례로 증가
    var cycle = 0       // 0: 왼쪽 아래로 이동 1: 오른쪽으로 이동, 2: 왼쪽 위로 이동
    var distance = 0    // 가장 바깥쪽 삼각형으로부터의 거리

    // 각 사이클마다 입력하는 숫자의 길이는 n, n - 1, n - 2, ..., 2, 1 순서로 줄어듦
    for length in (1...n).reversed() {
        for i in 0..<length {
            let row: Int
            let column: Int
            if cycle == 0 {
                row = (i + distance * 2 + 1) * (i + distance * 2) / 2
                column = distance
            } else if cycle == 1 {
                row = (n - 1 - distance + 1) * (n - 1 - distance) / 2
                column = i + distance + 1
            } else {
                row = (n - i - 1 - distance + 1) * (n - i - 1 - distance) / 2
                column = -1 - distance
            }
            answer[row + column] = number
            number += 1
        }

        cycle += 1
        if cycle == 3 {
            distance += 1
            cycle = 0
        }
    }

    // 디버그: 삼각형 모양으로 배열 출력
//    for i in 0..<n {
//        let rowIndex = (i + 1) * i / 2
//        print(answer[rowIndex..<(rowIndex + i + 1)])
//    }

    return answer
}

1. 일단 count :(n + 1) * n/2 로 전체배열의 길이를 파악해서 1차원 배열로 인덱스 접근하는게 더 효율적으로 느껴졌다. 이렇게 했으면 2차원 배열이라 계속 indexOutOfRange떴던거 생각하면 개발 효율성도 많이 올라갔을듯?
2. n층이라서 이걸 length in (1...n).reversed()이렇게 n개의 연필을 준비해서 뭔가 하나씩 쓰는 느낌? 을 잘 받았다. 이렇게 잘 세팅해놓으면 이제 중복으로 적힐일도 없으니까 너무 깔끔하게 느껴졌다.
   3.for문3개였던 나는 cycle로 단순화해주고 number를 적어주고 +1 해주는 부분을 공통적으로 수행하게끔해준 부분을 좀 차용해야겠다고 생각했다.