삼각달팽이 프로그래머스(C++)

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

---

제한사항

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

지금 이런 그림으로 보면 정삼각형 모양이지만 왼쪽 벽에 붙인다고 생각하면 각 층의 높이가 1, 2, ... n 인 직각 삼각형 모양이 된다.

이 점을 이용해서 처음 1부터 시작해서 내려가고 오른쪽으로 가고 왼쪽 위로 올라가는 로직을 구현하면 되는 문제다.

 

답이 1차원 배열이므로 1차원 배열으로 구현했다.

 

1. 왼쪽 아래로 가는 경우(아래로 가는 경우)

현재 인덱스에서 해당 층의 넓이 만큼을 인덱스에 더해주면 다음 위치다.

이 때 만약 더했는데 인덱스가 n*(n+1)/2 보다 크거나, 0이 아닌 경우에는 방향을 바꾼다.

 

2. 오른쪽으로 가는 경우

그냥 인덱스에 1씩 더하다가 다음 배열에 0이 아닌 값이 있으면 방향을 바꿔준다.

 

3. 위로 가는 경우(왼쪽 위)

현재 인덱스에서 해당 층의 넓이 만큼을 빼준다.

이 때 다음 위치가 0이 아닌 경우 방향을 바꾼다.

 

 

#include <string>
#include <vector>
 
using namespace std;
 
int ans[600000], dir, border[1001];
 
int move(int floor, int idx){
    int ret;
    switch(dir){
        case 1:
            return idx + floor;
        case 2:
            return idx + 1;
        case 3:
            return idx - floor;
    }
}
vector<int> solution(int n) {
    int width = 1, idx = 1;
    for(int i=1;i<1001;i++){
        border[i] = idx;
        width ++;
        idx += width;
    }
    vector<int> answer;
    int start = 0, end = n * (n + 1) / 2, fill = 0;
    dir = 1, idx = 1;
    while(fill < end)
    {
        fill++;
        ans[idx] = fill;
        int floor, next;
        for(int i=1;i<1001;i++){
            if(idx <= border[i]){
                floor = i;
                break;
            }
        }
        switch(dir){
            case 1:
                next = idx + floor;
                if(next > end || ans[next] != 0){
                    dir = 2;
                    idx = move(floor, idx);
                }
                else{
                    idx = move(floor, idx);
                }
                break;
            case 2:
                next = idx + 1;
                if(next > end || ans[next] != 0){
                    dir = 3;
                    idx = move(floor, idx);
                }
                else{
                    idx = move(floor, idx);
                }
                break;
            case 3:
                next = idx - floor;
                if(next <= 1 || ans[next] != 0){
                    dir = 1;
                    idx = move(floor, idx);
                }
                else{
                    idx = move(floor, idx);
                }
                break;
        }
    }
    for(int i=1;i<=end;i++){
        answer.push_back(ans[i]);
        // cout<<ans[i]<<' ';
    }
    return answer;
}
 

n이 최대 1000이므로 ans 행렬은 최대 1000*1001/2여야 한다. 근데 귀찮아서 60만이라 했다.

border는 해당 층의 넓이를 구한 함수다.

인덱스의 다음 위치를 구하기 위해서 현재 층의 두께가 필요해 구했다.