양의 정수 n이 주어지고 시계 방향으로 O(1) 추가 공간만 사용하여 n x n의 나선 행렬을 만듭니다.
나선 행렬은 원의 원점에서 시작하여 시계 방향으로 회전하는 나선처럼 작동하는 행렬입니다. 따라서 작업은 2 → 4 → 6 → 8 → 10 → 12 → 14 → 1 6 → 18에서 시작하여 O(1) 공간을 사용하여 나선 형태로 행렬을 인쇄하는 것입니다.
다음은 나선 행렬의 예입니다 -
예시
Input: 3 Output: 9 8 7 2 1 6 3 4 1
무한한 공간으로 코드를 푸는 것이 쉬워지지만, 그것은 최고의 프로그램이나 코드가 메모리와 시간 모두에서 효율적인 코드로 효율적이지 않습니다. 따라서 나선 순서를 유지하기 위해 행렬의 위쪽, 오른쪽, 아래쪽 및 왼쪽 모서리에 대해 각각 4개의 루프가 사용되지만 행렬을 오른쪽 위와 왼쪽 아래의 두 부분으로 나누면 개념을 직접 사용할 수 있습니다.
오른쪽 상단의 경우
mat[i][j] = (n-2*x)*(n-2*x)-(i-x)-(j-x)
왼쪽 하단의 경우
mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)
참고 - 2의 행렬 배수를 출력하는 프로그램을 작성 중입니다.
알고리즘
int spiralmatrix(int n) START STEP 1: DECLARE i, j, a, b, x STEP 2: LOOP FOR i = 0 AND i < n AND i++ LOOP FOR j = 0 AND j < n AND j++ FIND THE MINIMUM IN (i<j ) AND ASSIGN IT TO a FIND THE MINIMUM (n-1-i) < (n-1-j) AND ASSIGN IT TO b THEN ASSIGN THE LEAST VALUE FROM a AND b TO x IF i <= j THEN, PRINT THE VALUE OF 2* ((n-2*x)*(n-2*x) - (i-x) - (j-x)) ELSE PRINT THE VALUE OF 2*((n-2*x-2)*(n-2*x2) + (i-x) + (j-x)) END LOOP PRINT NEWLINE END LOOP STOP
예시
#include <stdio.h>
//For n x n spiral matrix
int spiralmatrix(int n){
int i, j, a, b, x; // x stores the layer in which (i, j)th element exist
for ( i = 0; i < n; i++){
for ( j = 0; j < n; j++){
// Finds minimum of four inputs
a = ((i<j ? i : j));
b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
x = a < b ? a : b;
// For upper right half
if (i <= j)
printf("%d\t ", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
// for lower left half
else
printf("%d\t ", 2*((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
}
printf("\n");
}
}
int main(int argc, char const *argv[]){
int n = 3;
spiralmatrix(n);
return 0;
} 출력
위의 프로그램을 실행하면 다음 출력이 생성됩니다 -
18 16 14 4 2 12 6 8 10