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

1. 문제 개요

https://programmers.co.kr/learn/courses/30/lessons/68645

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

1-1. 설명

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

삼각 달팽이 이미지

 

1-2. 제한사항

 - n은 1이상 1,000 이하

---

2. 구현

2-1. 풀이

2차원 벡터를 n x n 크기만큼 0으로 초기화해준다. 그리고 이 배열에 반시계 방향으로 count를 주어 1씩 더하며 숫자를 채워준다. 방향은 up, down, right로 지정해주었다. 각 방향의 끝에 도달했거나, 원소가 존재하면 방향을 바꾸어 이어서 숫자를 채운다. 

2-2. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    int size = n * (n-1) / 2 + n; // 채워야할 숫자의 크기
    int count = 1; // 0을 대처할 정수
    int index1 = 0;
    int index2 = 0;
    // 2차원 배열의 index
    
    vector<vector<int>> list(n, vector<int>(n)); // n x n 크기의 vector
    string dir = "down";
    // down -> right -> up (반복)
    
    for (int i = 0; i < size; i++) {
        // 화살표 방향 지정
        if (dir == "down"){ // 아래로 향할 때
            list[index1][index2] = count;
            count++;
            if (index1 + 1 == n || list[index1 + 1][index2] != 0) {
                dir = "right";
                index2++;
            }
            else index1 += 1;
        } else if (dir == "right"){ // 오른쪽으로 향할 때
            list[index1][index2] = count;
            count++;
            if (index2 +1 == n || list[index1][index2 + 1] != 0){
                dir = "up";
                index1--;
                index2--;
            }
            else index2 += 1;
        } else if (dir == "up") { // 위로 향할 때
            list[index1][index2] = count;
            count++;
            if (list[index1 - 1][index2 - 1] != 0) {
                dir = "down";
                index1++;
            }
            else {
                index1 -= 1;
                index2 -= 1;
            }
        }
    }
    
    for (int i = 0; i < n ;i++){
        for (int j = 0; j < n ; j++){
            if (list[i][j] != 0) answer.push_back(list[i][j]);
        }
    }
    // 저장된 2차원 벡터를 1차원 벡터에 저장
    return answer;
}