프로그래머스 - 정수를 나선형으로 배치하기 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer(n, vector<int>(n, -1));

    int dirX[4] = { 1,0,-1,0 };
    int dirY[4] = { 0,1,0,-1 };

    int dir = 0;

    int count = n;

    for (int i = 0; i < count; i++)
    {
        answer[0][i] = i + 1;
    }
    dir++;
    count--;

    int curX = n - 1, curY = 0;
    int cnt = n + 1;

    for (int k = count; k >= 0; k--)
    {
        for (int i = 0; i < k; i++)
        {
            curY += dirY[dir];
            curX += dirX[dir];
            answer[curY][curX] = cnt++;
        }
        dir = (dir + 1) % 4;
        for (int i = 0; i < k; i++)
        {
            curY += dirY[dir];
            curX += dirX[dir];
            answer[curY][curX] = cnt++;
        }
        dir = (dir + 1) % 4;
    }

    return answer;
}

 

설명

이 문제를 해결하기 위해 떠올렸던 아이디어는 다음과 같다. 

 

n = 4 일 때,

* 나선형으로 돌면 처음엔 오른쪽으로 4번 그 후, 아래 왼쪽으로 각각 3번 그 후, 위 오른쪽으로 2번씩 움직이며 숫자를 넣는다. 

따라서

1. 우->하->좌->상 방향으로 4->3->3->2->2->1->1 번씩 움직이면 되겠다는 것을 규칙으로 발견해냈다. 

dirY, dirX, dir 이 방향에 관련한 변수들이고, k for문과 cnt 가 몇번 움직여야하는지를 나타내는 변수와 어떤수를 넣어야하는지를 나타내는 변수이다. 

 

처음 for문으로 n번 오른쪽으로 이동하는 것을 처리한 후, 

k for문을 이용해 n-1번씩 2번 이동하는 것을 구현했다. 

또 한 방향이 끝날 때마다 dir변수를 1 증가시켜 방향을 전환시킨다. 

 

dirX, dirY 는 배열에서 각 방향으로 움직이기 위한 수이다. 

ex) 0번 인덱스인 오른쪽으로 이동하기 위해서는 밑으로 0칸, 오른쪽으로 1칸 dirX[0] = 1; dirY[0] = 0;