[프로그래머스][C++] 삼각 달팽이

삼각 달팽이

문제 링크

삼각 달팽이

분석

크기가 n인 삼각형 배열을 만들어야 합니다.

방향이 아래 -> 오른쪽 -> 위로 반복됩니다.
방향의 전환은 n번입니다.
방향이 전환될 수록 길이가 1씩 감소합니다.

마지막 숫자의 크기는 $\frac{n \times (n + 1)}{2}$입니다.

풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    
    // 달팽이 삼각형을 저장할 2차원 배열
    vector<vector<int>> snail(n, vector<int>(n));
    
    int x = 0, y = 0;   // 현재 위치
    int count = 1;  // 현재 숫자
    int dir = 0; // 방향
    
    for (int i = 0; i < n; ++i)
    {
        switch (dir)
        {
            // 아래로 이동
            case 0:
                for(int j = i; j < n; ++j)
                {
                    snail[y][x] = count;
                    ++count;
                    ++y;
                }

                dir = 1;
                ++x;
                --y;
                break;
            // 오른쪽으로 이동
            case 1:
                for (int j = i; j < n; ++j)
                {
                    snail[y][x] = count;
                    ++count;
                    ++x;
                }
                
                dir = 2;
                x -= 2;
                --y;
                break;
            // 왼쪽위로 대각선 이동
            case 2:
                for (int j = i; j < n; ++j)
                {
                    snail[y][x] = count;
                    ++count;
                    --x;
                    --y;
                }
                
                dir = 0;
                ++x;
                y += 2;
                break;
            default:
                break;
        }
    }
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i + 1; ++j)
        {
            answer.push_back(snail[i][j]);
        }
    }
    
    return answer;
}

2차원 배열로 x와 y위치를 저장하고, 방향을 사용하는 방법으로 풀었습니다.

각 방향별로 n - i번 반복되어 값이 추가됩니다.

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 삼각 달팽이를 만드는 반복문 $O(n(n + 1) / 2) \approx O(n^2)$
• 반환 배열에 저장하는 반복문 $O(n^2)$
• $O(n^2 + n^2)$

공간 복잡도는 $O(n^2)$입니다.

• 2D 배열 vector<vector<int>> snail(n, vector<int>(n)) $O(n^2)$
• 반환 배열 vector<int> answer $O(n(n + 1) / 2) \approx O(n^2)$
• $O(n^2 + n^2)$

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.2MB)
테스트 4 〉 통과 (1.10ms, 4.63MB)
테스트 5 〉 통과 (1.11ms, 4.61MB)
테스트 6 〉 통과 (1.18ms, 4.74MB)
테스트 7 〉 통과 (157.56ms, 107MB)
테스트 8 〉 통과 (165.24ms, 107MB)
테스트 9 〉 통과 (182.93ms, 107MB)