[프로그래머스][LV.2][C++]삼각 달팽이

 

반시계 방향으로 달팽이 채우기를 진행한 결과를 1차원 벡터로 반환해줘야한다.

반시계 방향으로 진행할때 총 3단계를 거친다

1. 아래로 이동

2. 오른쪽으로 이동

3. 위로 이동

 

일단 2차원벡터를 0으로 초기화시켜둔 다음 진행한다.

1단계 : 아래로 이동

아래로 이동에서 고려해야할 점은 단계가 진행될 수록 열과 끝나는 부분이 달라야한다는 점이다

열은 증가해야하고 끝나는 부분을 줄어들어야한다.

그리고 다 이동하고 나서는 오른쪽으로 이동할 위치를 지정해주기 위해 

 

2단계 : 오른쪽으로 이동

2단계에서 고려해야할 점은 행과 끝나는 범위의 열이다.

열은 전에 했던 부분에서 1 증가값에서 시작해서  채워진부분 전까지 진행하고

행은 단계별로 감소해야한다.

 

3단계 : 위쪽으로 이동

3단계에서 고려해야할 점은  끝나는 범위의 행과 열이다.

행은 이전값의 하나 전 인덱스에서 채워진 인덱스앞까지이고

열은 단계별로 감소해야한다.

 

구현을 잘 해야하는 문제인데 이해하기가 정말 어려웠다. 쓰고나서도 어려운 문제라 여러번 다시 봐야겠다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> triangle;
    
    if(n==1){
        answer.push_back(1);
        return answer;
    }
    
    for(int i=1;i<=n;i++){              //트라이앵글 모양 잡아주기
        vector<int>tmp;
        for(int j=0;j<i;j++) tmp.push_back(0);
        triangle.push_back(tmp);
    }
    
    int col=0,row=0;
    int num=1;
    int turn=0;                 //turn 한단계가 끝날수록 증가 -> 값이 들어갈 수 있는 곳 범위, 전체-turn 반복횟수
    while(true) {
        if (triangle[col][row] > 0) break;          //만약 채워져있는 칸이라면 끝
        
        for(int i=col;i<n-turn;i++){            //아래로 이동 
            if(triangle[i][turn]==0){
                triangle[i][turn]=num++;
                col=i; row=turn;
            }else break;
        }
        row+=1; turn+=1;        //채워져있는 거 다음 부분부터 
        
        for(int j=row;j<=n-turn;j++){            //오른쪽으로 이동 
            if(triangle[n-turn][j]==0){             //
                triangle[n-turn][j]=num++;
                col=n-turn; row=j;
            }else break;
        }
        col-=1;         //채워져있는거 이전 부터
        
        for(int k=col;k>=turn;k--){         //끝~채워진거 앞까지 위로
            if(triangle[k][k-turn+1]==0){              //k~1번째 까지
                triangle[k][k-turn+1]=num++;
                col=k; row=k-turn+1;
            }else break;
        }
        col+=1;
    }
    
    for(int i=0;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++) answer.push_back(triangle[i][j]);
    }
    return answer;
}