[프로그래머스] Lv.2 삼각 달팽이 (Swift) 문제풀이

26190 단어 swift알고리즘swift

프로그래머스 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
}
  1. 달팽이가 지나가면서 담을 정수 배열을 만들자

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

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

for _ in 0...n {
	let temp = [Int]()
    snailArr.append([temp, temp])
    // [[-- down, straight일 때 담길 배열 --], [-- up일 때 담길 배열 --]]
}
  1. 여러가지 변수를 선언한다
  • 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 이다
  1. 달팽이가 움직이기 시작한다
  • while문으로 반복하는데 number의 값이 달팽이가 갈 수 있는 숫자보다 많으면 안된다
    • 달팽이가 갈 수 있는 숫자의 최댓값 = n(n+1)2{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
이렇게 왔다갔다 하면서 봐야한다

  1. 먼저 배열에 숫자 넣는 것 부터 하자
  • 바깥 쪽 삼각형만 일단 넣는다고 생각하면 편하다
        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 // 몇 개가 들어갔는지 체크해주는 역할
        }
  1. 방향을 다 지난 후
	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
            }
        }
  1. 리턴 값 만들기
  • 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)

좋은 웹페이지 즐겨찾기