[Programmers] #181832 - 정수를 나선형으로 배치하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

n × n의 달팽이 배열을 만드는 문제로 방향 배열을 활용하면 해결할 수 있다. 시계방향으로 회전하도록 방향 배열을 정의한 후, 다음 칸으로의 이동은 방향 배열을 통해 진행하며 다음 칸이 배열 내부면서 방문하지 않은 칸이면 방문 후 이동하는 과정을 반복하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N^2)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    public int[][] solution(int n) {
        int[][] arr = new int[n][n];
        int r = 0, c = -1, d = 1, num = 1;

        while (num <= n * n) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n || arr[nr][nc] != 0) {
                d = (d + 1) % 4;
                nr = r + dr[d];
                nc = c + dc[d];
            }

            arr[nr][nc] = num++;
            r = nr;
            c = nc;
        }

        return arr;
    }
}

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

vector<vector<int>> solution(int n) {
    vector<vector<int>> arr(n, vector<int>(n));
    int r = 0, c = -1, d = 1, num = 1;

    while (num <= n * n) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || arr[nr][nc] != 0) {
            d = (d + 1) % 4;
            nr = r + dr[d];
            nc = c + dc[d];
        }

        arr[nr][nc] = num++;
        r = nr;
        c = nc;
    }

    return arr;
}

def solution(n):
    arr = [[0] * n for _ in range(n)]
    dr = (-1, 0, 1, 0)
    dc = (0, 1, 0, -1)
    r, c, d, num = 0, -1, 1, 1

    while num <= n * n:
        nr, nc = r + dr[d], c + dc[d]
        if not (0 <= nr < n and 0 <= nc < n) or arr[nr][nc] != 0:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]

        arr[nr][nc] = num
        num += 1
        r, c = nr, nc

    return arr

---