[프로그래머스] 월간코드챌린지1 - 삼각 달팽이 (Swift 풀이)

programmers.co.kr/learn/courses/30/lessons/68645

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

 

일단 n이 무한대로 크다고 생각하고, 각 자리별로 결과 배열의 인덱스가 어떻게 배치되는지 그려보았다.

따라서, 각 층의 첫번째 칸의 인덱스는 f * (f+1) / 2와 같고,

결과 배열의 크기는 n * (n+1) / 2 와 같다.

 

규칙 찾기

0부터 n*(n+1)/2-1 까지의 숫자를 차례대로 배치할 때,

진행 방향은 총 3가지이다.

DOWN(↓), RIGHT(→), UP(↖)

그리고 삼각형의 크기가 n일때, 직진 횟수는 n번이다.

 

DOWN방향일 때

0회차

인덱스 0부터 시작 / +1,+2,+3 ... +(n-1) 씩 증가

총 n칸을 채운다.

1회차

인덱스 4부터 시작 / +3,+4,+5 ... +(n-2) 씩 증가

총 n-3칸을 채운다.

2회차

인덱스 12부터 시작 / +5,+6,+7 ... +(n-3) 씩 증가

총 n-6칸을 채운다.

 

k회차

2*k 층에서 오른쪽으로 k칸 떨어진 위치에서 시작.

2*k층의 맨 왼쪽 인덱스는 2k*(2k+1)/2이므로,

인덱스는 2k(k+1) 부터 시작한다.

+(2k+1), +(2k+2) ...+(n-k+1) 씩 증가한다.

총 n-3k칸을 채운다.

 

 

RIGHT 방향일 때

0회차 n-1층이므로

인덱스 (n-1)*n/2 + 1 부터 시작한다.

총 n-1칸을 채운다.

1회차 n-2층이므로

인덱스 (n-2)*(n-1)/2 + 2부터 시작한다.

총 n-4칸을 채운다.

2회차 n-3층이므로

인덱스 (n-3)*(n-2)/2 + 3부터 시작한다.

총 n-7칸을 채운다.

 

k회차

n-k-1층이므로

인덱스 (n-k-1)*(n-k)/2 + k + 1 부터 시작한다.

총 n-3k-1칸을 채운다.

 

 

 

UP 방향일 때

 

0회차

n-2층의 마지막칸이므로

인덱스 (n-2)*(n-1)/2 + (n-2) 부터 시작한다.

-(n-1), -(n-2), -(n-3) ...

총 n-2칸을 채운다.

1회차

n-3층의 마지막칸 -1 칸 이므로

인덱스(n-3)*(n-2)/2 + (n-3-1)부터 시작한다.

-(n-2), -(n-3), -(n-4) ...

총 n-5칸을 채운다.

2회차

n-4층의 마지막칸-2칸이므로

인덱스 (n-4)*(n-3)/2 + (n-4-2) 부터 시작한다.

-(n-3), -(n-2), -(n-1) ...

총 n-8칸을 채운다.

 

 

k회차

n-k-2층의 마지막칸 - k (= n-k-2-k)칸이므로

인덱스 (n-k-2)*(n-k-1)/2 + (n-2k-2) 부터 시작

-(n-k-1), -(n-k-2), -(n-k-3) ...

총 n-3k-2칸을 채운다.

 

 

 

풀이

결과 배열의 크기는 위에서 구했듯이, n(n+1)/2이다.

n(n+1)/2 크기의 Int형 배열을 선언하고, 모두 0으로 초기화해 둔다.

let arrayLength: Int = n * (n+1) / 2
var answer: [Int] = [Int](repeating: 0, count: arrayLength)

 

number라는 변수에 1을 저장하고 칸을 이동할때마다 1씩 증가시키며

배열의 특정 위치에 number 값을 저장할 것이다.

var number = 1

 

총 n번의 직진이 있는데, Down -> Right -> Up 3가지 방향을 돌아가면서 선택해야 한다.

for(direction in 0..<n) {
   if direction%3 == 0 {
       // DOWN
   } else if direction%3 == 1 {
       // RIGHT
   } else {
       // UP
   }
}

 

각 방향으로 숫자를 채워넣는 함수를 작성해준다.

하나의 함수가 실행되면 해당 방향으로 1회차가 진행된다.

여기서 count는, 해당 방향으로 (0회차부터) 몇회차를 돌렸는지를 의미하는 것이다.

예를들어, goDown(count:2) 이면 2회차이므로 인덱스 12부터 채우는 부분이다.

 

이 함수들은 soltuion 함수 내에 있는 변수에 접근 가능하도록 solution 함수 내부에 작성한다.

 

func goDown(count: Int) {
    /*시작인덱스*/ var index: Int = 2 * count * (count + 1)
    /*총반복횟수*/ let total: Int = n-3*count
    /*루프증가폭*/ let gap: Int = 2 * count + 1
       
    for i in 0..<total {
        answer[index] = number
        index += (gap + i)
        number += 1
    }
}

func goRight(count: Int) {
    /*시작인덱스*/ let index: Int = (n - count - 1) * (n - count) / 2 + count + 1
    /*총반복횟수*/ let total: Int = n - (3 * count) - 1
    /*루프증가폭 = 1*/
    
    for i in 0..<total {
        answer[index + i] = number
        number += 1
    }
}

func goUp(count: Int) {
    /*시작인덱스*/ var index: Int = (n - count - 2) * (n - count - 1) / 2 + (n - 2 * count - 2)
    /*총반복횟수*/ let total: Int = n - (3 * count) - 2 
    /*루프감소폭*/ let gap = n-count-1
        
    for i in 0..<total {
        answer[index] = number
        index -= (gap - i)
        number += 1
    }
}

 

이제 위에서 만들어 둔 조건문의 빈 칸을 채워준다.

for direction in 0..<n {
    if direction%3 == 0 { 
        goDown(count: direction/3) 
    } else if direction%3 == 1 {
        goRight(count: direction/3) 
    } else { 
        goUp(count: direction/3) 
    }
}

 

완성된 코드

import Foundation

func solution(_ n:Int) -> [Int] {
    
    let arrayLength: Int = n * (n+1) / 2
    var answer: [Int] = [Int](repeating: 0, count: arrayLength)
    var number = 1
    
    func goDown(count: Int) {
        var index: Int = 2 * count * (count + 1)
        let total: Int = n-3*count
        let gap: Int = 2 * count + 1
        
        for i in 0..<total {
            answer[index] = number
            index += (gap + i)
            number += 1
        }
    }
    
    func goRight(count: Int) {
        let index: Int = (n - count - 1) * (n - count) / 2 + count + 1
        let total: Int = n - (3 * count) - 1
        
        for i in 0..<total {
            answer[index + i] = number
            number += 1
        }
    }
    
    func goUp(count: Int) {
        var index: Int = (n - count - 2) * (n - count - 1) / 2 + (n - 2 * count - 2)
        let total: Int = n - (3 * count) - 2 
        let gap = n-count-1
        
        for i in 0..<total {
            answer[index] = number
            index -= (gap - i)
            number += 1
        }
    }
    
    for direction in 0..<n {
        if direction%3 == 0 { 
            goDown(count: direction/3) 
        } else if direction%3 == 1 {
            goRight(count: direction/3) 
        } else { 
            goUp(count: direction/3) 
        }
    }
    
    return answer
}