프로그래머스[Lv.2] - 삼각 달팽이

문제 설명

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

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

처음 문제를 보고서는 규칙이 있을지 찾아보았다.

근데 규칙을 찾을 수 없었다.

그래서 생각한 방법은 2차원 배열에 삼각 달팽이를 그린 뒤, 정답 배열에 옮기는 것이다.

삼각 달팽이를 그리는 방법은 달팽이를 그리는 것과 비슷한다.

즉, dy, dx를 이용하여 한 칸씩 이동하며 숫자를 증가시키면 된다.

이때, dy, dx가 4방향이 아닌 3방향으로 정하는 것이다.

vector<int> dy = {1, 0, -1};
vector<int> dx = {0, 1, -1};

범위를 벗어나거나 이미 기록된 칸이라면 방향을 바꾸면 된다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> snail(1'000, vector<int>(1'000, 0));
    
    vector<int> dy = {1, 0, -1};
    vector<int> dx = {0, 1, -1};
    
    int size = 0;
    for(int i = 1; i <= n; i++) size += i;
    
    int cursorY = 0;
    int cursorX = 0;
    int num = 1;
    int dir = 0;
    
    snail[cursorY][cursorX] = num++;
    
    for(int i = 1; i < size; i++)
    {
        cursorY += dy[dir];
        cursorX += dx[dir];
        
        if(cursorX < 0 || cursorX >= n || cursorY < 0 || cursorY >= n)
        {
            cursorY -= dy[dir];
            cursorX -= dx[dir];
            
            dir = (dir + 1) % 3;
            
            cursorY += dy[dir];
            cursorX += dx[dir];
        }
        
        if(snail[cursorY][cursorX] != 0)
        {
            cursorY -= dy[dir];
            cursorX -= dx[dir];
            
            dir = (dir + 1) % 3;
            
            cursorY += dy[dir];
            cursorX += dx[dir];
        }
        
        snail[cursorY][cursorX] = num++;
    }
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(snail[i][j] != 0)
            {
                answer.push_back(snail[i][j]);
            }
        }
    }
    
    return answer;
}

---