프로그래머스 Lv.2 삼각달팽이

요약

1. 달팽이가 가는 방향을 3가지로 분류할 수 있다
   • up, down, straight
   • down -> straight -> up : 이 순서대로 달팽이는 움직인다
2. 달팽이가 삼각형의 한 변을 지나갈 때
   • 갈 수 있는 부분을 나누자
   • 
   • 위 그림과 같이 나누면 한변에서 갈 수 있는 길이는 (변의 길이 - 1)
3. 세 가지 방향을 다 돌고나면
   • 안쪽 삼각형으로 들어오게 된다
   • 
   • 안쪽 삼각형의 한 변의 길이는 (바깥 쪽 삼각형의 한 변의 길이 - 3)이다
   • 이때 단순히 3 이 아니라 위쪽에서 2, 아래쪽에서 1이라는 점을 알아두자
4. 1, 2, 3 번을 똑같이 반복한다

설명

1. 방향을 정의하자

enum Direction: String {
    case down
    case straight
    case up
}

2. 달팽이가 지나가면서 담을 정수 배열을 만들자

   up 방향은 숫자가 뒤에 추가되므로 이제 만들 정수 배열을 3차원 배열로 만든다

var snailArr = [[[Int]]]()

for _ in 0...n {
	let temp = [Int]()
    snailArr.append([temp, temp])
    // [[-- down, straight일 때 담길 배열 --], [-- up일 때 담길 배열 --]]
}

3. 여러가지 변수를 선언한다

• direction : 방향
• number : 배열에 추가될 정수 (달팽이가 지나가면서 밟은 숫자)
• step : 삼각형의 위쪽 인덱스
  • 바깥 쪽 삼각형에서 안쪽 삼각형으로 들어갈 때, 요약에서 설명한 것처럼 "위에서 2 아래서 1"이라서 -> 위에서 숫자가 늘어갈 것이다
• count : 달팽이가 어느 곳을 밟고 있는지 나타내는 인덱스
  • 삼각형에서 가로 한 줄씩이라고 생각하면 된다
• side : 삼각형의 한 변의 길이 및 삼각형의 맨 마지막 줄
  • 바깥 쪽 삼각형에서 안쪽 삼각형으로 들어갈 때, 요약에서 설명한 것처럼 "위에서 2 아래서 1"이라서 -> 아래서 숫자가 줄어들 것이다

var direction: Direction = .down // 처음은 down부터 시작한다
    
var number = 1 // 달팽이가 1부터 밟는다
var step = 1 // 달팽이가 처음 시작하는 곳은 삼각형의 맨 윗줄이다
var count = step // 맨 윗줄의 인덱스 값은 step 이다
var side = n // 삼각형의 한 변의 길이는 n 이다

4. 달팽이가 움직이기 시작한다

• while문으로 반복하는데 number의 값이 달팽이가 갈 수 있는 숫자보다 많으면 안된다
  • 달팽이가 갈 수 있는 숫자의 최댓값 = ${n(n+1)} \over {2}$ (등차수열의 합 공식)

while true {
	if number > n * (n + 1) / 2 { break }
    
    ...
}

다음에 나오는 5, 6번 순서는
down -> straight -> up 순으로 움직이므로
5 - down - 6 -> 5 - straight - 6 -> 5 - up - 6
이렇게 왔다갔다 하면서 봐야한다

5. 먼저 배열에 숫자 넣는 것 부터 하자

• 바깥 쪽 삼각형만 일단 넣는다고 생각하면 편하다

        switch direction {
        case .up:
            snailArr[count][1].insert(number, at: 0) // 아래서 위로 올라온다, up은 맨 끝에서 부터 추가되야하므로
            number += 1 // 달팽이가 밟을 때 마다 +1
            count -= 1 // 배열을 지나가면서(거꾸로) 추가할 수 있게 하는 인덱스 역할
        case .down:
            snailArr[count][0].append(number) // 위에서 아래로 내려온다
            number += 1 // 달팽이가 밟을 때 마다 +1
            count += 1 // 배열을 지나가면서 추가할 수 있게 하는 인덱스 역할
        case .straight:
        	// straight일 때는 맨 밑줄을 쭉 채워주면 되기 때문에
            snailArr[side][0].append(number)
            number += 1 // 달팽이가 밟을 때 마다 +1
            count += 1 // 몇 개가 들어갔는지 체크해주는 역할
        }

6. 방향을 다 지난 후

	switch direction {
        case .up:
            if count <= step { // 달팽이가 up일 때, 한 변에서 갈 수 있는 최대 길이는 "step + 1"이므로
                direction = .down // 방향 전환
                step += 2 // 위에서 2 늘어나고
                count = step
                side -= 1 // 밑에서 1 줄어든다
            }
            
        case .down:
            if count >= side { // 달팽이가 한 변에서 갈 수 있는 최대 길이는 "side - 1"이므로
                direction = .straight // 방향 전환
                count = step // count 초기화
            }
            
        case .straight:
            if count >= side { // 달팽이가 한 변에서 갈 수 있는 최대 길이는 "side - 1"이므로
                direction = .up // 방향 전환
                count = side
            }
        }

7. 리턴 값 만들기

• snailArr를 3차원 배열로 만들었기 때문에 다음과 같이 리턴값을 이쁘게 만들어준다

	var ret = [Int]()
    
    for i in snailArr {
        for j in i[0] { ret.append(j) }
        for j in i[1] { ret.append(j) }
    }

전체 코드

import Foundation

enum Direction: String {
    case up
    case down
    case straight
}

func solution(_ n: Int) -> [Int] {
    
    var snailArr = [[[Int]]]()
    
    for _ in 0...n {
        let temp = [Int]()
        snailArr.append([temp, temp])
    }
    
    var direction: Direction = .down
    
    var number = 1
    var step = 1
    var count = step
    var side = n
    
    while true {
        if number > n * (n+1) / 2 {
            break
        }
        switch direction {
        case .up:
            if count <= step {
                direction = .down
                step += 2
                count = step
                side -= 1
            }
        case .down:
            if count >= side {
                direction = .straight
                count = step
            }
        case .straight:
            if count >= side {
                direction = .up
                count = side
            }
        }
        
        switch direction {
        case .up:
            snailArr[count][1].insert(number, at: 0)
            number += 1
            count -= 1
        case .down:
            snailArr[count][0].append(number)
            number += 1
            count += 1
        case .straight:
            snailArr[side][0].append(number)
            number += 1
            count += 1
        }
    }
    
    var ret = [Int]()
    
    for i in snailArr {
        for j in i[0] { ret.append(j) }
        for j in i[1] { ret.append(j) }
    }
    
    return ret
}

결과

테스트케이스	결과
테스트 1	통과 (0.08ms, 16.5MB)
테스트 2	통과 (0.07ms, 16.4MB)
테스트 3	통과 (0.07ms, 16.6MB)
테스트 4	통과 (1.21ms, 17.4MB)
테스트 5	통과 (1.26ms, 17.1MB)
테스트 6	통과 (1.25ms, 17.3MB)
테스트 7	통과 (109.01ms, 108MB)
테스트 8	통과 (106.34ms, 108MB)
테스트 9	통과 (105.59ms, 108MB)