Programmers - 삼각 달팽이

---

title: Programmers - 삼각 달팽이
date: 2022-06-22
tags:

• Algorithm

---

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

문제 요약

정수 n이 주어지면 주어진 사진처럼 피라미드 방식으로 노드를 배치한다. 노드는 좌상단에서 우하단 순서이며, 우측 먼저 이동 후 다음 라인으로 이동하는 순서이다. 최상단 노드에서 최외곽부터 반시계로 모든 노드를 도는 달팽이가 방문한 순서를 각 노드에 저장하여, 이를 배열로 return한다.

문제 풀이

파스칼의 삼각형이 순간적으로 떠올랐다. 파스칼의 삼각형과는 다르지만, 이 덕분에 규칙성을 찾을 수 있었다.

파스칼의 삼각형은 대각선으로 움직일 때 증가값에 규칙이 존재한다. 이를 응용하여 n=4일 때 문제의 삼각형은 다음과 같이 풀 수 있다.

1번 위치를 시작으로 n-1 만큼 좌하단, 우측, 좌상단으로 이동한다. 좌하단 이동시 현재 level값만큼 index가 증가한다. 우측은 1씩만 증가하며, 좌상단 이동시 현재 level값만큼 index가 감소한다.
좌상단으로 n-1 만큼 이동하면 시작 위치로 돌아오게 된다. 외곽의 삼각형에 대한 처리가 끝났으므로 다시 중간 삼각형으로 가야 하며, 우하단으로 1회 이동 후 좌하단으로 1회 이동하면 된다.
1회 처리 후 n짜리 삼각형이 n-3짜리 삼각형으로 바뀐다. n=2,3의 경우 각각 1,2씩 움직이는 삼각형이 이루어진다. 하지만 n=1의 경우 유일하게 중앙에 한 개의 노드만 남으므로 이에 대한 처리만 따로 해주면 된다.
아래 그림은 위의 설명을 일반화하여 적용한 그림이다.

3의 길이만큼 줄어든 동일한 작업이 반복된다는 점에서 프랙탈을 연상할 수 있다.

프로그램은 위에서 해준 것을 그대로 처리해주면 된다.
불필요하게 프로그램이 길어지는 것을 방지하여 선호하지 않지만 후위증감연산자 또한 사용하였다.

프로그램

#include <vector>

using std :: vector ;

vector < int > solution ( int n )
{
    vector < int > answer ;
    answer.resize ( ( n * ( n + 1 ) ) / 2 ) ;
    int * ipTemp = answer.data () ;
    int iLen = ( n * ( n + 1 ) ) / 2 ;
    int iLevel = 1 ;                            // level of index
    int iIndex = 0 ;
    int iCnt = 0 ;



    --n ;
    while ( iCnt < iLen )
    {
        if ( iCnt + 1 == iLen )                    // only one node left
        {
            ipTemp [ iIndex ] = ++ iCnt ;

            break ;
        }


        for ( int i = 0 ; i < n ; ++i )            // Left down = Current + level
        {
            ipTemp [ iIndex ] = ++ iCnt ;
            iIndex += iLevel ++ ;
        }
        for ( int i = 0 ; i < n ; ++i )            // Right = Current + 1
        {
            ipTemp [ iIndex ++ ] = ++ iCnt ;
        }
        for ( int i = 0 ; i < n ; ++i )            // Left up = Current - level
        {
            ipTemp [ iIndex ] = ++ iCnt ;
            iIndex -= iLevel -- ;
        }

        n -= 3 ;                                // Start node, so need to move right down and left down
        iIndex += iLevel ++ ;                    // Right down = Current + level + 1
        iIndex += ++ iLevel ;                    // Left down = Current + level
    }


    return answer ;
}