Golang Algorithm - 정수를 나선형으로 배치하기

 

 

 

 

문제 설명
양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

제한사항
1 ≤ n ≤ 30
입출력 예
n   result
4   [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
5   [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]


입출력 예 설명
입출력 예 #1

예제 1번의 n의 값은 4로 4 × 4 배열에 다음과 같이 1부터 16까지 숫자를 채울 수 있습니다.

행 \ 열   0   1   2   3
0   1   2   3   4
1   12  13  14  5
2   11  16  15  6
3   10  9   8   7
따라서 [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]를 return 합니다.

입출력 예 #2

예제 2번의 n의 값은 5로 5 × 5 배열에 다음과 같이 1부터 25까지 숫자를 채울 수 있습니다.

행 \ 열   0   1   2   3   4
0   1   2   3   4   5
1   16  17  18  19  6
2   15  24  25  20  7
3   14  23  22  21  8
4   13  12  11  10  9
따라서 [[1, 2, 3, 4, 5], [16, 17, 18, 19, 6], [15, 24, 25, 20, 7], [14, 23, 22, 21, 8], [13, 12, 11, 10, 9]]를 return 합니다.

 

다음은 이 문제를 해결하기 위한 Go 소스코드다.

주석을 보면 로직을 알 수 있다.

로직의 흐름은 다음과 같다. 

1. 결과의 흐름을 담을 배열을 선언한다.
2. for문으로 각 배열 값을 0으로 채워준다.

3. 이동 방향에 따른 디렉션 인덱스 이중 배열을 선언한다. 
4. 첫 업데이트 함수는 1로 지정하고 반복문을 통해 4 x 4 (N * N) 크기보다 작거나 같을 경우 반복문을 동작하게 한다. 
5. 다음 배열위치로 이동할 변수 nextRow, nextCol을 지정한다.
6. nextRow,  nextCol 변수가 N * N 배열 크기를 넘어서면 dirIdx 배열의 인덱스를 업데이트한다. 이것이 의미하는 바는 

오른쪽으로 이동하던 배열에서 아래로 이동하게끔 하는 것이고 이후에는 다시 왼쪽 다시 위쪽 그리고 다시 오른쪽으로 이동하는 나선방향으로 배열이 순회하게끔 조건문을 작동시킨것이다.

7. row와 col에 방향 인덱스 값을 설정하고 num 변수를 1 증가시킨다. 이 때 num은 반복문 조건때문에 1을 증가시키고 이게 1,2,3,4,5,6,7,8,9~~16까지 증가하면서 동작한다. 이런식으로 계속 반복문으로 순회하면 나선방향으로 배열이 순회한다.

 

 

 

Go 소스코드

package main

import "fmt"

func solution(n int) [][]int {

	//결과로 쓸 배열을 정의한다.
	//이중 배열 선언
	res := make([][]int, n)

	// 	res [[] [] [] []]
	// [0 0 0 0]
	// [0 0 0 0]
	// [0 0 0 0]
	// [0 0 0 0]
	//이중 배열 크기만큼 순회해서 res 배열에 원소 설정
	fmt.Println("res", res)
	for i := range res {
		res[i] = make([]int, n)
		fmt.Println(res[i])
	}

	//움질일 방향을 설정하기 위해 다음 변수를 설정하자.
	//오른쪽으로 이동, 아래로 이동, 왼쪽으로 이동, 위로 이동
	//하단의 if 문 안에 dirIdx 변수를 통해 방향을 확인할 수 있다.
	dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

	//현재 위치 및 방향 초기화
	//행, 열, 나선방향, 위,오른쪽,왼쪽,아래
	row, col, dirIdx := 0, 0, 0

	//배열에 채울 숫자 초기화
	num := 1

	//배열을 모두 채울때까지 반복
	for num <= n*n {
		//현재 위치에 숫자 채우기
		//1로 채우기
		res[row][col] = num
		fmt.Println("res", res)
		nextRow, nextCol := row+dirs[dirIdx][0], col+dirs[dirIdx][1]
		fmt.Println("nextRow", nextRow, "nextCol", nextCol)
		//다음 위치가 배열의 범위를 벗어나거나 이미 숫자가 채워져 있는 경우 방향을 바꿈
		//경계를 넘을 때 dirIdx가 업데이트 된다.
		//처음에는 오른쪽으로 이동하다가 경계를 넘으면 아래로 이동하게끔 업데이트 된다. 따라서 dirIdx는0에서 1로 변경된다.
		if nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || res[nextRow][nextCol] != 0 {
			dirIdx = (dirIdx + 1) % 4
			//0 + 1 % 4 = 1 오른쪽 이동에서 아래로 이동
			//1 + 1 % 4 = 2 아래 이동에서 왼쪽으로 이동
			//2 + 1 % 4 = 3 왼쪽 이동에서 위쪽으로 이동
			//3 + 1 % 4 = 0 위로 이동에서 오른쪽으로 이동
			fmt.Println("check dirIdx", dirIdx)
		}

		//다음 위치로 이동
		fmt.Println("row1", row)
		fmt.Println("col1", col)
		row += dirs[dirIdx][0]
		col += dirs[dirIdx][1]
		fmt.Println("row2", row)
		fmt.Println("col2", col)
		//채널 숫자 증가
		num++
	}

	return res
}

func main() {

	n := 4
	solution(n)
}

 

 

소스코드를 실행했을 때의 결과입니다~

나는 머리가 안 좋아서  하나씩 데이터를 찍어봐야 알 수 있다. 
그래서 다음 데이터를 대입 하면서 로직을 생각하면 이해가 될 것이다. Go 코드 공부 파이팅!!

 

res [[] [] [] []]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
res [[1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
nextRow 0 nextCol 1
row1 0
col1 0
row2 0
col2 1
res [[1 2 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
nextRow 0 nextCol 2
row1 0
col1 1
row2 0
col2 2
res [[1 2 3 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
nextRow 0 nextCol 3
row1 0
col1 2
row2 0
col2 3
res [[1 2 3 4] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
nextRow 0 nextCol 4
check dirIdx 1
row1 0
col1 3
row2 1
col2 3
res [[1 2 3 4] [0 0 0 5] [0 0 0 0] [0 0 0 0]]
nextRow 2 nextCol 3
row1 1
col1 3
row2 2
col2 3
res [[1 2 3 4] [0 0 0 5] [0 0 0 6] [0 0 0 0]]
nextRow 3 nextCol 3
row1 2
col1 3
row2 3
col2 3
res [[1 2 3 4] [0 0 0 5] [0 0 0 6] [0 0 0 7]]
nextRow 4 nextCol 3
check dirIdx 2
row1 3
col1 3
row2 3
col2 2
res [[1 2 3 4] [0 0 0 5] [0 0 0 6] [0 0 8 7]]
nextRow 3 nextCol 1
row1 3
col1 2
row2 3
col2 1
res [[1 2 3 4] [0 0 0 5] [0 0 0 6] [0 9 8 7]]
nextRow 3 nextCol 0
row1 3
col1 1
row2 3
col2 0
res [[1 2 3 4] [0 0 0 5] [0 0 0 6] [10 9 8 7]]
nextRow 3 nextCol -1
check dirIdx 3
row1 3
col1 0
row2 2
col2 0
res [[1 2 3 4] [0 0 0 5] [11 0 0 6] [10 9 8 7]]
nextRow 1 nextCol 0
row1 2
col1 0
row2 1
col2 0
res [[1 2 3 4] [12 0 0 5] [11 0 0 6] [10 9 8 7]]
nextRow 0 nextCol 0
check dirIdx 0
row1 1
col1 0
row2 1
col2 1
res [[1 2 3 4] [12 13 0 5] [11 0 0 6] [10 9 8 7]]
nextRow 1 nextCol 2
row1 1
col1 1
row2 1
col2 2
res [[1 2 3 4] [12 13 14 5] [11 0 0 6] [10 9 8 7]]
nextRow 1 nextCol 3
check dirIdx 1
row1 1
col1 2
row2 2
col2 2
res [[1 2 3 4] [12 13 14 5] [11 0 15 6] [10 9 8 7]]
nextRow 3 nextCol 2
check dirIdx 2
row1 2
col1 2
row2 2
col2 1
res [[1 2 3 4] [12 13 14 5] [11 16 15 6] [10 9 8 7]]
nextRow 2 nextCol 0
check dirIdx 3
row1 2
col1 1
row2 1
col2 1