(C++) - 프로그래머스(월간 코드 챌린지 시즌 1) : 삼각 달팽이 답

programmers.co.kr/learn/courses/30/lessons/68645?language=cpp

코딩테스트 연습 - 삼각 달팽이

재귀 또는 일반적인 구현으로 풀 수 있는 문제였습니다.

 

풀이방법

 1. 먼저 삼각형을 적절히 변형해 생각합니다. 정삼각형이 아닌 직각삼각형이라고 생각하면 인덱싱이 편합니다.

 

 2. 다음과 같은 높이가 n인 직각삼각형을 만들기 위해서는 3가지 방향으로 수를 채워야 합니다.

   2-1. (1)번 방향 : 아래로 수직하강합니다.

   2-2. (2)번 방향 : 우측으로 평행하게 이동합니다.

   2-3. (3)번 방향 : 좌측 상단 대각으로 이동합니다.

    (1) -> (2) -> (3) 순으로 방향을 n번 바꾸어가며 수를 채워준다면 정답 수열을 만들 수 있습니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    int snail[1001][1001];
    int x = 0, y = 0, state = 0, num = 1;
    for(int i = 0; i < n; i++){
        if(state == 0){
            for(int j = i; j < n; j++)
                snail[x++][y] = num++;
            x--; y++;
            state = 1;
            continue;
        }
        
        if(state == 1){
            for(int j = i; j < n; j++)
                snail[x][y++] = num++;
            x--; y-=2;
            state = 2;
            continue;
        }
        
        if(state == 2){
            for(int j = i; j < n; j++)
                snail[x--][y--] = num++;
            x+=2; y++;
            state = 0;
        }
    }
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(snail[i][j]) answer.push_back(snail[i][j]);
    return answer;
}