[알고리즘]프로그래머스 68645번 - 삼각 달팽이

프로그래머스 68645번 - 삼각 달팽이

프로그래머스 68645번 - https://programmers.co.kr/learn/courses/30/lessons/68645

 

요구사항

1. 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 반환하라.

 

요구사항 분석 및  풀이과정

위 사진에서 주어진 삼각형(n=4)을 우리가 다루는 이차원 배열의 형태로 시각화해보면 다음과 같습니다.

 

 

이렇게 이차원 배열로 시각화한 후, 기존 삼각형에서 반시계 방향으로 달팽이 채우기를 시각화해보겠습니다.

 

 

달팽이 채우기를 위해서 칸을 이동하는 방향에 규칙성이 보이시나요?

 

1번 화살표 방향 -> 2번 화살표 방향 -> 3번 화살표 방향 -> 1번 화살표 방향 -> ... ->

 

지금은 n = 4 일 때의 삼각형이지만, n에 따라 그려보시면 1번, 2번, 3번 화살표의 방향이 계속 반복되는 것을 확인하실 수 있습니다.

 

행을 y라는 변수로, 열을 x라는 변수라고 하면 각 화살표 방향의 증감을 표현해보면 다음과 같습니다.

 

1번 화살표 방향 = (0, 1)

2번 화살표 방향 = (1, 0)

3번 화살표 방향 = (-1, -1)

 

그리고 그림을 살펴보면 방향 전환(화살표)은 n번 이루어지는 것을 알 수 있습니다. 바로 떠오르지 않는다면 n = 5, 6 일 때를 그려보시면 도움이 될 것 같습니다.

 

단, 우리는 원점 (0, 0) 또한 숫자를 채워야 하므로 원점에서 시작하는 것이 아니라 원점에서 첫 번째 방향인 1번 화살표 방향의 역방향으로 1칸 전인 (-1, 0)에서 시작하는 것으로 가정하겠습니다.

 

그러면 그림을 살펴보면 각 화살표 방향 내의 칸 이동은 k(1 <= k <= n) 번째 화살표일 때 n-k+1번 일어남을 알 수 있습니다.

 

계산의 편의를 위해서 k가 1부터 n까지 증가하는 것이 아니라 n부터 1까지 감소한다고 하면 각 화살표 방향 내의 칸 이동은 k번 일어남 또한 알 수 있습니다.

 

칸 이동이 일어날 때마다 숫자를 1부터 증가시켜서 이차원 배열을 채우게 되면 우리가 원하는 결과를 얻을 수 있습니다.

 

board[currentY][currentX] = num++

 

단, 1번 화살표 방향부터 3번 화살표 방향이 반복되야하므로 나머지 연산을 통하여 방향이 반복되도록 설정해주어야 합니다.

 

dir = (dir + 1) % 3

 

그리고 결과는 이차원 배열에 담긴 수를 행 우선으로 한 줄로 펼친 일차원 배열을 반환하여야 하므로, 이차원 배열을 적절히 순회하여 결과를 생성하여 주면 됩니다.

 

소스코드 작성

class Solution {

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

	public int[] solution(int n) {
		int currentY = -1;
		int currentX = 0;
		int dir = 0;
		int num = 1;

		int[][] board = new int[n][n];
		for (int k = n; k > 0; k--) {
			for (int i = 0; i < k; i++) {
				currentY = currentY + dy[dir];
				currentX = currentX + dx[dir];
				board[currentY][currentX] = num++;
			}
			dir = (dir + 1) % 3;
		}

		int[] result = new int[(n * (n + 1)) >> 1];
		int idx = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x <= y; x++) {
				result[idx++] = board[y][x];
			}
		}

		return result;
	}
}

 

결과

 

소스코드 깃허브 주소

링크