[Programmers.co.kr/Swift] 삼각 달팽이

Programmers.co.kr/코딩테스트 연습 - 월간 코드 챌린지1 - 삼각 달팽이 (Lv. 2)

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

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

---

TODO :

정수 n이 매개변수로 주어집니다.

다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후,

첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

Constraints : 

• n은 1 이상 1,000 이하입니다.

Sample Input :

n
4
5
6

Sample Output :

result
[1,2,9,3,10,8,4,5,6,7]
[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

Solution.swift : 

//  Created by Yongwoo Marco on 2021/02/20.
//  Copyright © 2020 Yongwoo Marco Kim. All rights reserved.
//
import Foundation

func solution(_ n:Int) -> [Int] {
    var snail = [[Int]](), num = 1, f = 0, l = 0
    var fN = n, lN = n, limit = 0 // 멈춤 포인트 값
    var point = ["down", "right", "up"]
    
    for i in 1...n {
        limit += i
        let middle = [Int](repeating: 0, count: i)
        snail.append(middle)
    }

    var now = point[0]
    
    while num <= limit {
        snail[f][l] = num
        
        switch now {
        case point[0]:
            if f+1 == fN {
                now = point[1]
                l += 1
            } else {
                f += 1
            }
        case point[1]:
            if l+1 == lN {
                now = point[2]
                f -= 1
                l -= 1
            } else {
                l += 1
            }
        case point[2]:
            if f-1 == n-lN {
                now = point[0]
                f += 1
                fN -= 1
                lN -= 2
            } else {
                f -= 1
                l -= 1
            }
        default:
            break
        }
        num += 1
    }
    
    return snail.reduce([]){ $0 + $1 }
}

How I tried this :

보자마자 많이 풀어보진 못했지만.

dy = [0, 1, 0, -1]

dx = [-1, 0, 1, 0]

같은 방향 문제인걸 깨달았다.

위 내용은 밑에서 설명하기로 하고

 

생각보다 문제는 아주아주 간단하다.

단순히 늘어가는 숫자가 순차적으로 제 위치로 가면된다.

 

코드를 나누어 보며 간단히 설명하고자 한다.

func solution(_ n:Int) -> [Int] {
    var snail = [[Int]](), num = 1, f = 0, l = 0
    var fN = n, lN = n, limit = 0 // 멈춤 포인트 값
    var point = ["down", "right", "up"]
    
    // ...
    
}

선언부

제공된 그림과 달리 n=4

[ [1], [2, 9], [3, 10, 8], [4, 5, 6, 7] ]

처럼 2차원 배열로 구현하려고 한다. snail = [[Int]]()

 

방문할때 마다 입력할 수 num

2차원 배열의 좌표 값 snail[ f ][ l ]

 

개인적으로 먼가 C++이나 자바처럼 [y][x] 좌표와 dy, dx 로 덧셈하면서 

방문하는게 삼각형이라 어색하기도 하고 다르게 구현해 보고 싶어서

 

point = ["down", "right", "up"] 라고 키 값을 주고

상황에 맞게 switch를 이용하려고 생각했다

 

n 이 2정도 이상 커지는 경우마다 안에 삼각형을 한번씩 더 돌게된다

그렇기 때문에 처음 돌때 삼각형과 안쪽에 삼각형을 돌때

for문을 돈다면 마지막 인덱스가 다르다

그래서 그 마지막 인덱스가 중간에 변환해야 하니 fN, lN으로 각각의 제한점을 두었다.

limit 는 n = 4 라고 주어진다면 마지막 방문수 10 같은 제한을 정했다.

func solution(_ n:Int) -> [Int] {
    // 선언부 ...
    
    for i in 1...n {
        limit += i
        let middle = [Int](repeating: 0, count: i)
        snail.append(middle)
    }

	// ...
}

수열처럼 3, 10, 8 을 얻어낼 수 있는 방법은 없고 

그림 그리듯 자리를 방문하면서 수를 입력 해야 하므로 

[ [0], [0, 0], [0, 0, 0], [0, 0, 0, 0] ] / n = 4 

미리 할당 해두었다. 세번째 배열의  두번째 인덱스 보다 세번째 인덱스를 먼저 방문하기 때문에 (10보다 9를 먼저 방문)

.append 나 .insert가 아닌 직접 방문을 해야해서 미리 배열을 만들고 

limit 값도 구했다.

func solution(_ n:Int) -> [Int] {
	// ...
    
    var now = point[0]
    
    while num <= limit {
        snail[f][l] = num
        
        switch now {
        case point[0]:
            // ... down 좌측 모서리 내려오기
        case point[1]:
            // ... right 아래 모서리 이동하기
        case point[2]: 
            // ... up 우측 모서리 올라가기
        default:
            break
        }
        num += 1
    }
    
    return snail.reduce([]){ $0 + $1 }
}

point 배열을 이용해서 3가지 상황을 주고 좌표를 진행 시킨다.

 

point[0] "down" 인 경우 말그대로 배열 좌측을 따라 이동한다. 

point[1] "right" 인 경우는 현재 2차 배열의 우측으로 이동한다.

point[2] "up" 인 경우는 현재 위치 [fN][lN]에서 우측 모시를 따라 올라간다.

 

물론 n = 4 라면 num 이 10일때 딱 한번만 이동하고 끝나지만 

어찌보면 위 과정을 할려고 했지만 fN와 lN으로 제한하고 limit로 마치게 

구현을 했다.

 

snail[f][l] = num 이 현재 변경된 좌표에 수를 입력하고

switch 문을 통해 다음 좌표로 이동하는 구현을 했다.

 

조금 디테일하고 내 공부다 생각해서 엑셀로 한땀 한땀 정리를 해보았다. 예제 (n = 6)

첫번째 삼각형사이클

1. point[0] "down"

case point[0]:
    if f+1 == fN {
    	now = point[1]
    	l += 1
    } else {
    	f += 1
    }
      

최초 시작은 f = 0, l = 0으로 시작 한다

코드에서 f+1 == fN 

현재 [5][0] 라면 f+1 == 6 == fN = n = 6 

 

가장 마지막 배열에 도착한거고 

현재 상태 point[1]로 변경 -> 오른쪽으로 이동하는 상태

 

구현자체를

[5][0]은 방문했기 때문에

오른쪽 이동 하는 상태는 [6][0]을 방문하면서 시작하기 위해

l -> l + 1

까지 구현했다.

 

위 경우처럼 마지막으로 도착하지 않는 다면 

f -> f + 1

아래로 좌표를 이동시켰다.

 

 

2. point[1] "right"

case point[1]:
   if l+1 == lN {
	 now = point[2]
	 f -= 1
	 l -= 1
   } else {
	 l += 1
   }

1. 에서 설명이 길었어서 간단히 보면

if l+1 == lN {} 마찬가지로 [5][5] 에 도착하면 

상태를 바꿔주고 [4][4]로 이동한다

else {} 는 이차 배열에 l -> ㅣ+ 1 이동한다.

3. point[2] "up" 

case point[2]:
   if f-1 == n-lN {
      now = point[0]
      f += 1
      fN -= 1
      lN -= 2
   } else {
      f -= 1
      l -= 1
   }

if f - 1 == n - lN {}

마지막 리미트 포인트이다.

코드만 보면 설명이 너무 부족해서 풀어 보자면

[1][1] 까지 왔다면 한번의 사이클이 끝나는 점이다.

삼각형이 크다면 [1][1] -> [1+1][1]의 자리가 

다음 사이클의 시작점이 될 예정이다.

 

n은 최초 삼각형의 제한을 의미하고

lN은 최초 삼각형의 [][ l ] 좌표의 리미트이다.

 

n : 6 / lN : 6  

f - 1 = 1 - 1 = 0 == 6 - 6

최초 시작점인 0 이 f - 1 이면

상태를 다시 내려가는 down으로 바꾸고

f -> f + 1 / 시작점이 [0][0] 에서 [2][1] 로 바뀌고 삼각형이

n = 6 에서 n = 4로 바뀌기 때문에 fN과 lN의 크기도 변경했다.

다음 사이클을 위해 시작점 이동

두번째 삼각형 사이클

 

1-1. point[0] "down"

2-1. point[1] "right"

3-1. point[2] "up"

n 이 홀 수 인 경우는 

두번째 사이클의 시작점까지 이동하며 끝나고

 

n 이 짝 수 인 경우는 

마지막 사이클이 끝나는 점에서 마친다.

 

What I got is : 

 

I have to study :

이중 배열을 이용해 좌표로 방향 찾기

dy = [0, -1, 0, 1]

dx = [-1, 0, 1, 0]

 

현재 좌표를 [y][x] 라고 가정했을때

 

이중배열을 지도처럼 펼쳤다고 가정하자면

엑셀로 직접 한땀한땀 ㅠㅠ

for i in 0...3 {
   y += dy[i]
   x += dx[i]
    
   print(arr[y][x])
}

이런 식으로 코드 함수를 가지고 있다면 

한번에 상하좌우 (물론 나의 코드는 좌상우하, dx, dy 인덱스 차이로 바꿀수 있다) 의 데이터를 확인 할 수 있다.

 

DFS BFS등 다양한 알고리즘에서 사용된다

문제에 관한 모든 저작권 : https://programmers.co.kr/

 

프로그래머스