[Java] 2차원 배열 - 달팽이 만들기
문제
아래 와 같은 형태로 데이터를 저장하는 이차원 배열을 생성하세요.
문제 풀이
주어진 문제 보기와 같이 달팽이 모양의 2차원 배열을 만들어야 한다.
여기서 배열을 잘 살펴보면, 안쪽으로 말려 들어가는 달팽이 집과 같은 모양을 보이고 있음을 알 수 있다.
이 원리를 코드로 구현하기 위한 아이디어를 생각해보자.
아이디어 도출
정사각형 형태의 배열이기에 가로 열과 세로 행은 같다고 보고, 2차원 배열 안에 채워지는 숫자를 어떻게 채워갈지 정해보자.
- 1부터 5까지는 첫번째 행에 오른쪽으로 채워지며 5부터 9까지는 5번째 열에 아래로 채워진다.
- 10부터 13까지는 5번째 행에서 왼쪽으로 채워지며, 13부터 16까지는 1번째 열에서 위로 채워진다.
- 16부터 19까지는 2번째 행에서 오른쪽으로 채워지며, 19부터 21까지는 4번째 열에서 아래로 채워진다.
- 21부터 23까지는 4번째 행에서 왼쪽으로 채워지며, 23부터 24까지는 2번째 열에서 위로 채워진다.
- 마지막으로 24에서 25로 3번째 행에서 채워지게 된다.
여기서 총 5번의 과정을 통해 1부터 25까지 달팽이 모양으로 2차원 배열을 채우게 되는데 이 5번이라는 것은 정사각형의 행, 열과 동일한 숫자임을 알 수 있다.
이 때, 5번 만큼 배열을 채울 때 일반적인 배열의 순서대로 오른쪽이나 아래로 채워지는 경우와, 배열의 순서와는 반대인 왼쪽이나 위로 채워지는 경우를 분기하여 채우도록 하면 된다. 그리고 채워질 수는 계속해서 증가시키며 행*열만큼의 수가 되도록 하면 된다.
오른쪽이나 아래로 채워지는 경우
위 1번 과정과 같이 원래 순서대로 자연스럽게 채워야 하는 경우를 살펴보자.
먼저 열에 값을 오른쪽 방향으로 채운 뒤, 행에 값을 아래 방향으로 아래와 같이 채우게 된다.
i가 행 인덱스, j가 열 인덱스라고 한다면 i는 0행으로 고정시키고, j만 1씩 증가시켜서 1~5까지 첫 행을 채워주어야 한다.
그리고 첫 행 채우기가 끝나면 열 인덱스 j를 고정시키고, i만 1씩 증가하며 채워주어야 한다.
단, 첫 열을 채울 때는 5-1번만큼 반복하여 6부터 9까지만 채우면 된다는 점을 유의해야 한다.
왼쪽이나 위로 채워지는 경우
1번 과정대로 배열을 채웠다면 10부터 13까지, 14부터 16까지는 반대 방향으로 배열을 채워야 한다.
이 때는 열 인덱스인 j를 1씩 감소시켜서 채워야 하기 때문에 방향을 반대로 바꿔줄 변수가 하나 있어야 한다.
문제 예시처럼 가로 5, 세로 5 크기를 가지는 정사각형을 채우려면 위 과정을 5번 반복하여 달팽이 배열을 채울 수 있게 된다.
아이디어가 생각보다 복잡해보이지만 필자가 장황하게 늘어놓은 점도 없지 않기에 코드를 작성하면서 이해하는 것이 더 쉬울 수 있다.
자 그럼 이제 코드를 작성해보자.
1
2
3
4
5
6
int[][] answer = new int[col][row];
int i = 0 // row start index
int j = -1; // col start index
int tmp = 0; // snail number
int direction = 1; // i with j switch direction(1 or -1)
int repeat = row; // repeat count
달팽이 모양대로 채워줄 2차원 배열 answr를 선언한다. 그리고 i는 행 인덱스, j는 열 인덱스를 의미하고 tmp는 각 배열에 채워줄 숫자 값이 된다.
j가 -1부터 시작하는 이유는, 행을 고정하고 열을 증가시키며 배열에 채워줄 때 배열의 범위를 벗어나지 않도록 하기 위함이다.
direction 변수는 방향이 바뀔 시 사용될 스위치 변수이며, repeat는 몇 번을 반복해야 하는지를 알려주는 반복 인덱스라고 보면 된다.
여기서는 정사각형이기 때문에 행과 열의 크기가 같기에 둘 중 아무거나 repeat로 선언해도 무방하다.
1
2
3
while(repeat > 0) {
...
}
기본적으로 repeat가 0이 될 때까지 반복하면 된다. 문제 예시대로라면 5번을 반복하게 된다.
while문에서 2차원 배열을 채우는 반복문을 작성해주면 되며, while문의 탈출 조건은 반복 인덱스인 repeat가 0과 작거나 같아지는 순간이다.
1
2
3
4
5
6
for(int l=0; l<repeat; l++) {
tmp++;
j = j + direction;
answer[i][j] = tmp;
}
repeat--;
앞에서 구상한 아이디어대로 행 인덱스인 i를 고정해둔 채 j를 1씩 증가시키며 첫 행을 1부터 채워준다.
이 때, 열을 고정시키고 행을 증가시켜야 하는데 행의 첫번째 값은 이전에 채워졌으므로, 채워진 값 이후로 배열을 채우기 위해 repeat 변수를 1 감소시킨다.
1부터 5까지 5번을 반복하며 첫 행에 채워진다.
1
2
3
4
5
6
7
for(int m=0; m<repeat; m++) {
tmp++;
i = i + direction;
answer[i][j] = tmp;
}
direction *= -1;
다음으로는 행 인덱스만 변경하며 배열을 채워주어야 하기 때문에 j를 고정해둔 채 행 인덱스인 i를 1씩 증가시키며 열 값을 채워준다.
6부터 9까지 4번을 반복하며 마지막 열에 채워진다.
이제 다시 배열의 행부터 값을 채워야 하는데 왼쪽이나 위 방향인 반대로 채워야 하기 때문에 열 인덱스인 j를 1씩 감소시켜야 한다. 그래서 선언해둔 스위치 변수인 direction을 -1로 바꾸어주면 된다.
이렇게 while문 안에서 두가지의 반복 과정을 진행하며 repeat 반복 변수가 0 이하가 된다면 while문을 종료된다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
class Solution {
public int[][] solution(int row, int col) {
int[][] answer = new int[col][row];
int i = 0; // row start index
int j = -1; // col start index
int tmp = 0; // snail number
int direction = 1; // i with j switch direction(1 or -1)
int repeat = row; // repeat count
while(repeat > 0) {
for(int l=0; l<repeat; l++) {
tmp++;
j = j + direction;
answer[i][j] = tmp;
}
repeat--;
for(int m=0; m<repeat; m++) {
tmp++;
i = i + direction;
answer[i][j] = tmp;
}
direction *= -1;
}
for(int[] arr : answer) {
System.out.println(Arrays.toString(arr));
}
return answer;
}
public static void main(String[] args){
Solution sol = new Solution();
int row = 5;
int col = 5;
sol.solution(row, col);
}
}
회고
- 행과 열을 탐색하는 순서를 전환하기 위해 양수와 음수를 이용할 수 있었고, 열을 고정시키고 행을 1씩 증가시켜서 열 값을 채워주고 행을 고정시키고 열 값을 1씩 증가시켜서 행 값을 채워줄 수 있었다.