LeetCode알고리즘 Spiral Matrix II

오늘은 59번 문제인 Spiral Matrix II를 풀어보겠습니다.
중간 난이도이고 59.5%의 성공률을 보이네요.


오늘의 주제는 matrix 행렬입니다.
먼저 문제를 살펴볼게요!

양의 정수 n이 주어지고, 1부터 n^2까지 나선형 순서로 숫자를 채워 n x n의 행렬을 만들어내라.
제약조건으로는 n이 1이상 20이하네요.

아래 예시를 보면 바로 이해되실거에요.

1번 예시는 n이 3으로 들어왔고 나선형 순서로 1부터 9까지 채워나가는거에요.
2번 예시는 n이 1으로 들어왔고 나선현 순서로 1부터 1까지 채워나가는거에요.
그리고 채워진 2차 행렬을 그대로 리턴해주면 됩니다.

TMI 예전에.. 정처기(정보처리기사) 시험을 쳐본적이 있는데 언제지... 4년 전인가...
그 시험에서 요 문제가 나왔었어요.
이번 알고리즘 문제로 만나게 되어 뭔지 모르게 반가웠던..

다시... 문제로!
제가 풀고자 한 방식은 matrix라는 2차원 배열을 생성해주고 n^2값으로 채워넣습니다.
n^2값으로 채워넣는 이유는 행렬에서 최대로 가질 수 있는 값이 n*n이기도하고 횟수를 줄일 수 있기도 합니다.
num은 돌면서 채워나갈 수를 의미하고
top, right, bottom, left는 행렬의 인덱스를 의미합니다.
while조건문으로 top < bottom, left < right를 주었습니다. (스위프트에서 ,콤마는 and연산을 말합니다)
총 4번의 for루프를 돌게되는데 여기서 나선형 순서로 돌면서 num값을 채워주는 방법입니다.

코드는 아래와 같습니다.

func generateMatrix(_ n: Int) -> [[Int]] {
    var matrix = Array(repeating: Array(repeating: n * n, count: n), count: n)
    var num = 1
    var top = 0
    var right = n - 1
    var bottom = n - 1
    var left = 0

    while top < bottom, left < right {

        for i in stride(from: left, to: right, by: 1) {
            matrix[top][i] = num
            num += 1
        }

        for i in stride(from: top, to: bottom, by: 1) {
            matrix[i][right] = num
            num += 1
        }

        for i in stride(from: right, to: left, by: -1) {
            matrix[bottom][i] = num
            num += 1
        }

        for i in stride(from: bottom, to: top, by: -1) {
            matrix[i][left] = num
            num += 1
        }

        top = top + 1
        right = right - 1
        bottom = bottom - 1
        left = left + 1

    }

    return matrix
}

예제 1번을 그림으로 나타낸다면 아래와 같습니다.

2차원 배열을 생성해주고 n^2값으로 채워주고 변수들을 생성해주는 초기 단계입니다.
후에 while조건에 성립하니 for루프를 총4번 돌면서 나선형으로 num을 채워줍니다.

여기까지가 while에 진입하고 4번의 for 루프를 끝내는 과정입니다.
그리고 각각의 값을 더해주고 빼주죠.

그리고 다시 while 조건문을 확인해주는데 성립이 되지 않습니다.
(여기서 n^2로 값을 초기화 했기 때문에 한 번 더 들어가지 않아도되는 이점이 있습니다)
(만약 0으로 초기화 했다면 한 번 더 들어가서 9를 넣어줘야겠죠!)

마지막으로 채워넣은 matrix를 리턴해주는 방법입니다.
그리고 제출
(퍼포먼스는 언어마다 다르니 각 언어에서 런타임, 메모리 사용량을 비교하시길..)

resource:
https://leetcode.com/problems/spiral-matrix-ii/