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

문제 설명

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

제한사항

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

---

풀이

50분
수학적으로 간단한 풀이법을 30분 동안 고민했으나, 결국 동작 방식을 그대로 옮기는 코드를 작성하게 되었다. 다른 풀이를 참고하더라도 이 문제는 시뮬레이션으로 접근하는 것이 맞는 것 같다. 알고리즘 분류를 미리 알고 풀이를 시작하는데 익숙해져버린 것은 아닌지 걱정이다. 문제를 풀기 전에 방향성에 대해 충분히 고민하도록 하자.

코드

// 08:20 ~ 09:10
#include <string>
#include <vector>

using namespace std;

int dx[3] = {1 , 0, -1};
int dy[3] = {0 , 1, -1};

vector<int> solution(int n) {
    int x =0, y=0, num = 1,dir = 0;
    vector<int> answer;
    vector<vector<int>> tree(n,vector<int>(n,0));
    
    int step = n;
    while(step > 0){
        for(int i =0; i< step; ++i){
            tree[x][y] = num;
            num += 1;
            if(i == step - 1) break;
            x += dx[dir];
            y += dy[dir];
        }
        dir = (dir + 1) % 3;
        x += dx[dir];
        y += dy[dir];
        step -= 1;
    }
    
    for(int i = 0; i< n; ++i){
        for(int j = 0; j < i +1; ++j) answer.push_back(tree[i][j]);
    }
    
    return answer;
}