문제 본문의 설명이 매우 직관적이고 예시 그림과 함께 보자

정수 n이 매개변수로 주어집니다.

다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서

맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후,

첫 행부터 마지막 행까지

모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

example.png

이와 같이 n 을 한 변의 길이로 하는 삼각형모양의 배열에서 값을 채워나가면 되는 문제다

그래서 이걸 어떻게 구현을 해야할까?

풀이⌗

먼저 삼각형 모양의 배열을 코드상에서 어떻게 나타낼까? 에 대해서 인데

2차원 배열이 일반적으로 도형의 각 위치별 값을 표현하기 쉽기에 2차원 배열로 표현하기로 했다.

다만, 정말로 삼각형 모양대로 배열을 만들려면 처리시에 계산하기가 힘들듯하여,

n 값이 4인 삼각형 예시로 이차원 배열을 아래와 같이 n의 크기대로 생성하여 처리하였다.

example3.png

그렇다면 이제 위에 그림과 같이 처리할 배열이 주어졌을때 안에 값을 넣어야 하는데

아래 그림의 화살표를 참고하여 보자면

example4.png

  1. (0,0) 에서 시작하여, (3,0)까지

  2. (3,1) 에서 시작하여, (3,3)까지

  3. (2,2) 에서 시작하여, (1,1)까지

  4. (2,1)값을 채워 넣으며 마무리.

좀 더 구현하기 쉽게 표현 해보자면

  1. (0,0)에서 시작하여 아래로 이동하며 값을 추가하면서 진행

  2. 마지막으로 값을 입력한 부분에서 우측 방향으로 값을 추가하면서 진행

  3. 마지막 부분에서 대각선 방향으로 값을 추가하면서 진행

  4. 더이상 진행하면서 값을 추가할 수 없을 경우 종료

정도로 표현할 수 있겠다.

이차원 배열을 순회하면서

값을 추가할 수 없는 경우 와 해당 진행방향으로 진행할 수 없는 경우

진행 방향을 아래, 오른쪽, 좌상향 대각선 으로 돌아가면서 진행하기에

해당 방향 표현을 위해 배열 두개로 진행 방향에 대한 정보를 담았다.

int[] dx = {0, 1, -1};
int[] dy = {1, 0, -1};

이후에는 이차원 배열을 (0,0) 부터 진행 방향대로 순회하면서 값을 넣어주면 처리된다.

값을 추가할 수 없는 경우 판단의 경우, 마지막으로 입력되는 값은 등비 수열의 합과 같으므로

$$ \sum_{k=1}^n k = \frac{n(n+1)}{2}$$

로 표현할 수 있다.

마지막으로 입력되는 값보다 다음 입력할 값이 클 경우

값을 추가할 수 없는 경우 중 하나로 판단하여 더이상 추가하지 않고 종료한다.

마지막으로 결과값을 일차원 배열에 담아 전달하여야 하는데

이차원 배열을 순회하며, 값이 입력된 값을 순차적으로 담아서 처리하였다.

public class Solution {

    // 2차원 배열 순회시 방향 지정용
	static int[] dx = {0, 1, -1};
	static int[] dy = {1, 0, -1};

	public int[] solution(int n) {

        // 위에 수식대로 수정하면 좀 더 깔끔...
        // 코드 작성시 단순히 반복을 통해 도출하였음
		int maxValue = 0;
		for (int i = 1; i <= n; i++) {
			maxValue += i;
		}
		int[][] map = new int[n][n];
        // 시작 좌표 설정
		int y = 0;
		int x = 0;
        // 시작 값 설정
		int startValue = 1;
        // 순회 시작 방향 설정
		int rotate = 0;
        // 2차원 배열 순회
		while (startValue <= maxValue) {
            // 배열의 크기를 넘어가거나
            // 해당 부분의 값이 이미 있을 경우
            // 해당 방향으로 진행을 멈춤
			while ((y >= 0 && y < n) && (x >= 0 && x < n) && (map[y][x] == 0)) {
				map[y][x] = startValue++;
				y += dy[rotate % 3];
				x += dx[rotate % 3];
			}
            // while문으로 마지막 진행을 취소하기 위해서 추가
			y -= dy[rotate % 3];
			x -= dx[rotate % 3];
            // 진행 방향 변경
			rotate++;
            // 다음 진행을 위해 검색 좌표 변경
			y += dy[rotate % 3];
			x += dx[rotate % 3];
		}
        // 최대값의 크기가 결과값 배열의 크기
		int[] answer = new int[maxValue];
		int idx = 0;
        // 2차원 배열을 순회하면서 결과값 처리
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
                // 값이 입력된 경우만 추가하여 처리
				if (map[i][j] != 0) { 
					answer[idx++] = map[i][j];
				}
			}
		}
		return answer;
	}
}

좀 더 깔끔하게 코드를 짜도록 노력하자…

참조⌗