[Programmers] Level2 : 삼각 달팽이

Question

---

Solution

• 삼각형을 1차원 배열에 채워 넣을때 좌변 -> 밑변 -> 우변 -> 좌변 순서로 값이 증가한다.
• n에 대한 만들어질 삼각형의 크기는 수열의 합 공식으로 인해 n(n+1)/2 로 쉽게 구할 수 있다.
• 각 변에 대해 바뀌는 시점은 idx가 n, n-1, n-2, n-3.. 이 된다.
• row와 column을 선언하고, 각 변에 대해 2차원 인덱스로 보면 다음과 같이 된다. 좌변: ++row 밑변: ++column 우변: –row, –column
• 2차원 배열에 담아진 값들을 이제 순서대로 answer에 해당 범위에 알맞게 옮겨주면 된다.

---

Cord

#include <string>
#include <vector>

#define MAX 1001

using namespace std;

int triangle[MAX][MAX];

vector<int> solution(int n)
{
    vector<int> answer;

    int total = n * (n + 1) / 2; // 수열의 합 공식

    // 배열의 가로, 세로
    int row = -1;
    int column = 0;

    int cnt = n; // n, n-1, n-2 ...
    int trigger = 0; // 삼각형의 각변에 대한 분기

    for (int i = 0; i < total; ++i)
    {
        if (i == cnt)
        {
            ++trigger;
            cnt += n - trigger;
        }

        switch (trigger % 3)
        {
        case 0: // 좌변 ( row 증가)
            ++row;
            break;
        case 1: // 밑변 ( column 증가)
            ++column;
            break;
        case 2: // 우변 (row와 column 감소)
            --row;
            --column;
            break;
        }

        triangle[row][column] = i + 1;
    }

    // 값 대입
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            answer.push_back(triangle[i][j]);
        }
    }

    return answer;
}

---

Result