62일 (2326. Spiral Matrix IV) matrix 다른 접근필요

You are given two integers m and n, which represent the dimensions of a matrix.

You are also given the head of a linked list of integers.

Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1.

Return the generated matrix.

 

Example 1:

Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
Explanation: The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.

Example 2:

Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

 

Constraints:

• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• The number of nodes in the list is in the range [1, m * n].
• 0 <= Node.val <= 1000

 

- 접근방법

 

한번도 접해본적이 없는 문제라 도저히 감이 안잡혀서 직관적으로 접근하였다. (디버깅도 안 되어서 구현에 엄청 오래걸림)

 

m*n이  4 *4 일때, 범위 조건을 4방향으로 나눴다.

1바퀴 순회가 끝났을때 시작인덱스는 (0, 0)에서 (1, 1)로 증가시키고, 마지막인덱스는 (m-1, n-1)에서 (m-2, n-2)로 감소시켰다.

 

 

- 코드

class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] answer = new int[m][n];
        int x = 0;
        int y = 0;
        int z = 0;
        int cnt = 0;
        int maxCnt = m*n;

        while (cnt < maxCnt) {
            if(head == null) head = new ListNode(-1); // head가 null이면 -1을 추가하고 아니라면 head.val를 추가.
            if(x == m-1 && y == n-1) answer[x][y] = head.val; // 3*3일때 중앙값

            if (x == z && y < n-1) { // 4방향으로
                answer[x][y++] = head.val;
            } else if (x < m-1 && y == n-1) {
                answer[x++][y] = head.val;
            } else if (x == m-1 && y > z) {
                answer[x][y--] = head.val;
            } else if (x > z && y == z) {
                answer[x--][y] = head.val;
                if(x == z) { // 1바퀴 순회시 시작인덱스 +1씩, 마지막인덱스는 -1씩
                    z++;
                    x = z;
                    y = z;
                    m--;
                    n--;
                }
            }

            head = head.next == null? null : head.next; // head.next가 null인지 판단.
            cnt++;
        }

        return answer;
    }
}

 

- 시계방향으로 한 바퀴를 4방향으로 나눠서 1번 순회시, 안쪽배열 시계방향 순회하는 방식 (많이 느리다.)

 

 

 

https://leetcode.com/problems/spiral-matrix-iv/

Spiral Matrix IV - LeetCode