[프로그래머스][월간코드챌린지 시즌1] 삼각 달팽이

위 예시 그림처럼 숫자를 삼각형으로 순환하며 배열에 삽입하는 문제이다.

 

저 그림을 배열에 넣기 쉽게 바꾸면 아래처럼 된다.

 

1) n = 4

1
2	9
3	10	8
4	5	6	7

 

2) n = 5

1
2	12
3	13	11
4	14	15	10
5	6	7	8	9

 

switch문에서 아래(0), 오른쪽(1), 위(2) 이렇게 세 방향을 dir 변수로 설정해주고, 각 dir에 맞게 배열을 채워넣는다.

한 방향으로 수를 채워넣는 횟수는 n, n-1, n-2 ... 1씩 줄어들기 때문에 반복문은 각 방향에 대해 아래와 같이 설정한다.

for(int i = 0; i < n; i++){
	for(int j = i; j < n; j++){
    		...
    }
}

 

 

arr[x][y]에서

i) 아래(0) 방향으로 갈 때

: x는 1씩 증가하고, y는 그대로 → arr[x++][y] = num++

 

ii) 오른쪽(1) 방향으로 갈 때

: x는 그대로, y는 1씩 증가 → arr[x][y++] = num++

 

iii) 위(2) 방향으로 갈 때

: x, y 모두 1씩 감소 → arr[x--][y--] = num++

 

 

특정 방향을 다 채운 후 방향을 변경할 때에는

i) 아래(0) → 오른쪽(1)

: x++, y-- 후 dir을 1로 변경

 

ii) 오른쪽(1) → 위(2)

: y-2, x-- 후 dir을 2로 변경

 

iii) 위(2) → 아래(0)

: x+2, y++ 후 dir을 0으로 변경

 

// 월간 코드 첼린지 시즌 1 : 삼각달팽이.cpp
#include <string>
#include <vector>
using namespace std;

vector<int> solution(int n) {
    vector<vector<int>> arr(n, vector<int>(n, 0));
    vector<int> answer;
    int x = 0, y = 0; // 좌표
    int num = 1; // 채워넣을 숫자
    int dir = 0; // 아래(0), 오른쪽(1), 위(2)
    
    for(int i = 0; i < n; i++){
        switch(dir){
            case 0: // 아래
                for(int j = i; j < n; j++){
                    arr[x++][y] = num++;
                }
                x--;
                y++;
                dir = 1;
                break;
            case 1: // 오른쪽
                for(int j = i; j < n; j++){
                    arr[x][y++] = num++;
                }
                y -= 2;
                x--;
                dir = 2;
                break;
            case 2: // 위
                for(int j = i; j < n; j++){
                    arr[x--][y--] = num++;
                }
                x += 2;
                y++;
                dir = 0;
                break;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(arr[i][j] != 0){
                answer.push_back(arr[i][j]);
            }
        }
    }
    return answer;
}