Algorithm) 프로그래머스(Lv2) - 삼각 달팽이 (구현)

 

안녕하세요 후르륵짭짭 입니다.

정말 오랜만에 알고리즘 문제를 올리는 것 같습니다.

그 동안 열심히 알고리즘 공부를 했는데,,, 사실 실력 향상이 Lv2에서 잘 안 오르는 것 같아여,, ㅠㅠ

이 문제도 오랫동안 생각하다가,,,, 잘 안 풀려서 다른 사람의 풀이를 보고 영감을 얻었습니다.

 

** 문제 해설 **

import Foundation

func solution(_ n:Int) -> [Int] {
    
    
    if n == 1 {
        return [1]
    }
    
    var total = 1
    
    for plus in 2...n{
        
        total = total + plus
        
    }
    
    var map : [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
    
    var number = 1
    var y = 0
    var x = 0
    var whatTodo = "D"
    
    var lastBottom = n - 1
    var firstTop = 0
    
    while number <= total {
        
        if whatTodo == "D"{
            
            map[y][x] = number
            
            if lastBottom == y {
                
                x += 1
                whatTodo = "R"
                lastBottom -= 1
                
            }
            else{
                y += 1
            }
            
        }
        else if whatTodo == "R"{
            
            map[y][x] = number
            
            if x + 1 == n || map[y][x + 1] != 0 {
                whatTodo = "T"
                y -= 1
                x -= 1
            }
            else{
                x += 1
            }
            
        }
        else if whatTodo == "T"{
            map[y][x] = number
            
            if y - 1 == firstTop {
                firstTop = y + 1
                whatTodo = "D"
                y += 1
            }
            else{
                y -= 1
                x -= 1
            }
        }
        
        number += 1
        
    }
    
    return map.flatMap { (ele) -> [Int] in
        return ele
    }.filter({$0 != 0})
}

방법은 정말,,, 어,,,,, 간단했습니다.

처음에 저는 이 문제를 일차원 배열로 풀려고 했는데,,,,

이게 아주 잘 못 된 생각이였습니다.

그렇게 풀 경우 너무 내용이 복잡해지고,,, 수리적인 영역이 많이 필요한데,

이차원 배열로 풀으니, 쉽게 해결 할 수 있었습니다.

 

이차원 배열로 문제를 풀어나간다면

Y 축이 곳 층의 높이가 됩니다.

그리고 x는 가로가 됩니다.

그런데 일차원 배열로 풀려고하면 허허허 등차수열 같이 풀어가야해서 힘들어 집니다.

 

해결하는 과정에서 중요한 것은 순서 입니다.

삼각 달팽이는 위에 그림 처럼

빨간색으로 내려 갔다가 파랑색 처럼 가로로 이동하고 노랑색에서 대각선으로 이동 합니다.

그리고 이 순서를 무한히 반복합니다.

 

그럼 언제 까지 하느냐!!!

마지막 순번일 때 까지 하면 됩니다.

우리가 채워 줄 공간은,

N = 1 : 1

N = 2 : 3

N = 3 : 6

N = 4 : 10

N = 5 : 15

이렇게 2 -> 3 -> 4 -> 5 이렇게 증가하고 있습니다.

그래서 우리가 원하는 마지막 값을 알 수 있게 됩니다.

var total = 1
    
    for plus in 2...n{
        
        total = total + plus
        
    }

그래서 이렇게 해준 겁니다.

 

그럼 이제 하나씩 알아보면

빨간색은 현재 X , Y 축이 있을 때,

Y 축만 1을 계속 더해서 내려가면 됩니다. 언제까지? N보다 작을 때 까지 ㅎㅎㅎ

그런데 만약 N의 위치에 도달한다면, 그땐 파랑색으로 변화 해주면 되죠.

 

파랑색은 머져? 가로로 움직이는 겁니다.

그래서 X축만 1을 계속 더해서 오른쪽으로 이동하면 됩니다.

언제까지? N의 범위를 넘어가지 않고 0이 아닐때 까지

여기서 왜 0이 아닐때 까지냐?하면 노랑색을 보면 알 수 있습니다.

 

이 그림을 다시 보면 맨 밑에 파랑색은 범위 전 까지 이지만

두번째 파랑색을 보면 노랑색 전 까지 입니다.

그러면 노랑색을 지나간 곳은 이미 숫자가 적혀진 부분 입니다.

또한 최소 숫자가 1 부터 시작하니깐 0은 나올 수가 없기 때문에

0이 아닐 때 까지 파랑색을 이동 시켜 줍니다.

 

그럼 노랑색은 머냐??

노랑색은 x도 한칸 뒤로 이동하고 y도 한칸 뒤로 이동 합니다.

그래야 쭉 올라가는 형태로 만들 수 있는데,

꺽이는 부분은 어떻게 구현 할 것이냐 하면

이 그림을 보면 18이 노랑색의 마지막 부분 입니다.

그런데 이 부분은 우리가 처음 시작한 1 바로 다음 아래 Y 값이죠.

바로 이겁니다. 이 부분 전까지 해주면 됩니다.

그런데 다음 27은 18이 아니라 19 까지 입니다.

그래서 변곡점인 부분을 Y + 1을 해주면 됩니다.

 

이것을 쭉 반복해주면 됐습니다.

 

알고리즘,,, 나랑 안맞습니다 ㅠㅠ 후우

 

참고 사이트 :

yabmoons.tistory.com/575

[ 프로그래머스 [ 월간코드챌린지 ] 삼각 달팽이 ] (C++)