[프로그래머스] (LV2) 삼각 달팽이

삼각 달팽이

JavaScript, Python

문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

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

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

풀이

---

javascript

function solution(n) {
    if (n === 1) return [1];
    
    var state = 0; // 아래 왼쪽 방향 시작
    var count = n;
    var value = 1;
    var currentFloor = 1;
    var currentIndex = 0;
    var answer = Array.from(Array(n*(n+1)/2),()=>0);

    while(count > 0){
        
        for(let i = 0; i < count; i++){

            answer[currentIndex] = value++;

            if(state === 0){ // 아래 왼쪽 방향
                
                if(i !== count-1)
                    currentIndex += currentFloor++;
                else{
                    currentIndex++;
                    state = 1;
                }
                
            } else if (state === 1){ // 오른쪽 방향
            
                if(i !== count-1)
                    currentIndex++;
                else{
                    currentIndex -= currentFloor--;
                    state = 2;
                }
                
            } else { // 왼쪽 위 방향
                
                if(i !== count-1)
                    currentIndex -= currentFloor--;
                else{
                    currentIndex += currentFloor++;
                    state = 0;
                }
            }
        }
        count--;
    }
    
    return answer;
}

python

def solution(n):
    floor = 1; index = 0; flags = 1; size = int(n * (n+1) / 2)
    answer = [0] * size

    for i in range(size):
        answer[index] = i+1

        index_count = {'1':floor,'0':1,'-1':-floor}
        next_index = index + index_count[str(flags)]
        
        if not (0 <= next_index < size) or answer[next_index] != 0:
            flags = (flags-1 if flags != -1 else 1)
        
        index = index + index_count[str(flags)]
        floor += flags
        
    return answer

설명

---

처음 접했을 때는, 반복되는 패턴의 삼각형을 기준으로 분할정복을 사용하려 했다.
하지만 각기 처리된 삼각형들의 매끄러운 병합 과정이 떠오르지 않았다.

그래서 n(n+1)/2 개의 숫자를 체우는 반복문을 만들어 한 번에 해결했는데,
매 번 현재의 층(floor)와 방향을 초기화하며 배열에 값을 할당한다.

javascript풀이에서는 count 변수를 이용해 첫 직선이 n칸을 할당하고,
그 다음 직선부터 1칸씩 감소한 4, 3, 2, 1칸을 할당하는 규칙성을 이용했다.

상태 개념을 이용할 것이라 count 활용은 굳이 필요 없는 방법이지만
최대한 분할정복 방법으로 풀어보려던 시도라고 보면 된다.

이와 다르게 Python 풀이는 깔끔하게 현재의 상태(층수, 방향)만 이용한다.
두 방법 모두 O(N²)의 시간복잡도를 나타낸다.

그 와중에 python의 a < X < b 연산 허용은 정말 적응이 안된다.