[프로그래머스 lv2] 삼각 달팽이 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

방향을 회전하며 좌표를 지나는 전형적인 시뮬레이션 문제이다.

삼각형에서 규칙을 찾아보면, 

 

 

n칸, n-1칸, n-2칸, ... 1칸씩 같은 방향으로 이동하면서 0번, 1번, 2번으로의 회전이 반복된다.

따라서 i = n 부터 i = 1까지 외부 반복문을 수행하면서 내부에서는 i칸만큼 같은 방향으로 이동하고 숫자를 기록하면 된다.

이 때, i번째 칸을 이동할 때는 방향이 전환되므로, 방향 변수 dir을 다음 회전 방향으로 변경하여 이동하도록 한다.

 

초기 좌표를 x = 0, y = 0 이라고 했을 때, 0번 방향으로의 움직임은 (+1, -0.5),  1번 방향으로의 움직임은 (0, +1), 2번 방향으로의 움직임은 (-1, -0.5)가 된다. 좌표를 이동하면서 (x좌표, y좌표, 숫자번호)를 저장해 두고, 이를 정렬하면 위에서 아래, 왼쪽에서 오른쪽 순서대로 숫자가 나열된다.  정렬을 이용하면 숫자들을 직접 배열에 기록할 필요가 없어 편리하다.

 

정렬된 결과를 바탕으로 숫자 값들만 추출하여 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ddi = tuple<double, double, int>;

#define X first
#define Y second

double dx[3] = {1, 0, -1};
double dy[3] = {-0.5, 1, -0.5};

vector<int> solution(int n) {
    
    vector<ddi> v;
    double x = 0, y = 0;
    int dir = 0, cnt = 1;
    
    for (int i=n; i>=1; i--) {
        for (int j=0; j<i; j++) {
            v.push_back({x, y, cnt++});
            if (j == i-1) dir = (dir+1)%3;
            x += dx[dir];
            y += dy[dir];
        }
    }
    
    sort(v.begin(), v.end());
    
    vector<int> ans;
    for (auto [x, y, num] : v) ans.push_back(num);
    return ans;
}