문제 68645. 삼각 달팽이

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

입력

• 정수 n

입력 제한

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

입력 예제

// input
4

// ans
[1,2,9,3,10,8,4,5,6,7]

 

풀이 방식

출력 결과물은 입력한 n의 크기만큼 빗변의 길이를 가지는 정삼각형에서 반시계방향으로 회전하며 수가 증가하는 모습을 가진다. n이 6인 정삼각형을 예시로 들면 아래 그림과 같다.

이번 문제는 해당 로직을 구현하기만 하면 되는 구현 문제이다. 따라서, 구현만 하면 더 이상 고려할 사항이 추가적으로 발생하지 않는다.

 

이 문제를 풀기 위해서는 발상을 살짝 바꿔주면 된다. 그림은 정삼각형이지만 왼쪽으로 밀어 직각삼각형을 만들어주면 풀이 방법이 눈에 보이게 된다. 동일하게 n이 6인 정삼각형을 예시로 들면 아래 표와 같다.

1
2	15
3	16	14
4	17	21	13
5	18	19	20	12
6	7	8	9	10	11

표를 보게 되면 감이 올 것이다. 이 문제는 2차원 배열을 만든 뒤 아래 -> 오른쪽 -> 왼쪽 위 대각선으로 반복적인 이동을 하면 된다. 여기에 이동할 수 없는 경우를 위해 예외 처리(2차원 배열의 범위를 넘어서거나, 이미 숫자가 들어있는 곳으로 이동하려는 경우 등)를 하고, 2차원 배열에서 들어있는 숫자들을 차례대로 1차원 배열에 넣으면 정답이 된다.

정답 코드 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int N;
bool inRange(int x, int y){
    return 0 <= x && x < N && 0 <= y && y < N;
}
vector<int> solution(int n) {
    vector<int> answer;
    N = n;
    
    vector<vector<int>> v1;
    v1.resize(n, vector<int>(n));
    
    int pos_x = 0, pos_y = 0;
    v1[0][0] = 1;
    int cnt = 2;
    bool end = false;
    while(!end){
        end = true;
        while(inRange(pos_x+1, pos_y) && !v1[pos_x+1][pos_y]){
            pos_x++;
            v1[pos_x][pos_y] = cnt;
            cnt++;
            end = false;
        }
        
        if(end) break;

        while(inRange(pos_x, pos_y+1) && !v1[pos_x][pos_y+1]){
            pos_y++;
            v1[pos_x][pos_y] = cnt;
            cnt++;
        }

        while(inRange(pos_x-1, pos_y-1) && !v1[pos_x-1][pos_y-1]){
            pos_x--; pos_y--;
            v1[pos_x][pos_y] = cnt;
            cnt++;
        }
    
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i+1; j++){
            //cout << v1[i][j] << ' ';
            answer.push_back(v1[i][j]);
        }
        cout << '\n';
    }
    return answer;
}