프로그래머스 - 삼각 달팽이 문제 링크

[문제]

문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• n은 1 이상 1,000 이하입니다.

입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

---

[풀이]

해설

• n*n 배열 중 삼각형에 값을 입력하는 것과 같다.
• 1부터 1~n까지 더한 값 max를 차례대로 입력한다.
  
  

1. 1~n까지 더한 값 max를 getMax 함수를 이용하여 구한다.
2. n*n 배열 중 실제로 값이 입력될 삼각 배열을 -1 로 초기화한다. (1~n행에 행의 값만큼 열이 이용된다. - 1행은 1열만, 3 행은 3행 초기화)
3. 달팽기 채우기 과정은 1)(↓)세로 채우기 2)(→)가로 채우기 3)(↖)대각선 채우기 총 3가지로 이루어져 있으며 입력되는 값이 max보다 작을 때 반복된다. (행 i, 열 j, 값 k)

	0) 모든 채우기 조건
 		 - k < max : k가 max보다 작을 것
	1)(↓)세로 채우기
    		- i + 1 < n : 배열 내의 행열인지 판단
        	- arr[i+1][j] < 0 : 이미 채워진 값이 아닐 것
    	2)(→)가로 채우기
    		- j + 1 < n : 배열 내의 행열인지 판단
        	- arr[i][j + 1] < 0 : 이미 채워진 값이 아닐 것
    	3)(↖)대각선 채우기
        	- i - 1 > 0 && i - 1 > 0 : 배열 내의 행열인지 판단
        	- arr[i - 1][j - 1] < 0 : 이미 채워진 값이 아닐 것

위의 각각의 조건이 만족할 때 세로로, 가로로, 대각선으로 k값이 증가하면서 값이 채워진다.
4. 삼각배열이 완성되면 삼각배열 초기화할 때 처럼 answer에 값을 입력한다.

코드

public static int[] solution(int n) {
	int[][] arr = new int[n][n];

	int max = getMax(n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			arr[i][j] = -1;
		}
	}

	int[] answer = new int[max];

	int i = 0, j = 0, k = 1;

	arr[i][j] = k;

	while (k < max) {
		while (i + 1 < n && k < max && arr[i + 1][j] < 0) {
			arr[++i][j] = ++k;
		}

		while (j + 1 < n && k < max && arr[i][j + 1] < 0) {
			arr[i][++j] = ++k;
		}

		while (i - 1 > 0 && i - 1 > 0 && k < max && arr[i - 1][j - 1] < 0) {
			arr[--i][--j] = ++k;
		}
	}

	k = 0;

	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			answer[k++] = arr[i][j];
		}
	}
	return answer;
}

static int getMax(int n) {
	return n == 1 ? 1 : getMax(n - 1) + n;
}