넘치게 채우기

[LeetCode] 2326. Spiral Matrix IV 본문

PS/LeetCode

[LeetCode] 2326. Spiral Matrix IV

riveroverflow 2024. 9. 9. 10:03
728x90
반응형

https://leetcode.com/problems/spiral-matrix-iv/description/?envType=daily-question&envId=2024-09-04

leetcode - Spiral Matrix IV

문제 유형 : 행렬, 연결 리스트

문제 난이도 : Medium

 

문제

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.

 

정수 m, n을 받는다. 주어진 연결리스트를 시계방향 spiral로 감아서 만든 m*n 행렬로 변환시키시오. 남은 공간은 -1로 채우시오.

맨위 왼쪽부터 시작하도록 합니다.

 

풀이

변수 rowStart, rowEnd, colStart, colEnd를 만든다.

각각 0, m-1, 0, n-1로 초기화한다. 이는 각 사이드를 채울 인덱스의 양 끝이 될 것이다.

 

맨 위줄을 채우면, row시작인덱스는 1 증가한다.

맨 오른쪽줄을 채우면, col의 끝인덱스가 1 감소한다.

맨 아래쪽줄을 채우면, row의 끝인덱스가 1 감소한다.

맨 왼쪽줄을 채우면, col의 시작인덱스가 1 증가한다.

 

이를 유의해서 순회시키면 된다. 중간에 head의 널체크도 유의하고, 처음부터 m * n을 -1로만 채운 2D 배열을 만들어놓아서 빈공간에 알아서 -1이 채워져있도록 하자.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m, vector<int>(n, -1));
        int rowStart = 0, rowEnd = m - 1;
        int colStart = 0, colEnd = n - 1;
        
        while (head && rowStart <= rowEnd && colStart <= colEnd) {
            for (int col = colStart; col <= colEnd && head; ++col) {
                ans[rowStart][col] = head->val;
                head = head->next;
            }
            rowStart++;
            
            for (int row = rowStart; row <= rowEnd && head; ++row) {
                ans[row][colEnd] = head->val;
                head = head->next;
            }
            colEnd--;
            
            for (int col = colEnd; col >= colStart && head; --col) {
                ans[rowEnd][col] = head->val;
                head = head->next;
            }
            rowEnd--;
            
            for (int row = rowEnd; row >= rowStart && head; --row) {
                ans[row][colStart] = head->val;
                head = head->next;
            }
            colStart++;
        }
        
        return ans;
    }
};

 

GO

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func spiralMatrix(m int, n int, head *ListNode) [][]int {
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, n)
        for j := range ans[i] {
            ans[i][j] = -1
        }
    }

    rowStart := 0
    rowEnd := m - 1
    colStart := 0
    colEnd := n - 1

    for head != nil {
        for col := colStart; col <= colEnd && head != nil; col++ {
            ans[rowStart][col] = head.Val
            head = head.Next
        }
        rowStart++

        for row := rowStart; row <= rowEnd && head != nil; row++ {
            ans[row][colEnd] = head.Val
            head = head.Next
        }
        colEnd--

        for col := colEnd; col >= colStart && head != nil; col-- {
            ans[rowEnd][col] = head.Val
            head = head.Next
        }
        rowEnd--

        for row := rowEnd; row >= rowStart && head != nil; row-- {
            ans[row][colStart] = head.Val
            head = head.Next
        }
        colStart++
    }

    return ans
}
728x90
반응형