[프로그래머스] 삼각 달팽이 - Java

https://programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

---

문제

문제 설명

정수 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]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

---

풀이

풀이 과정

반시계 방향으로 삼각형을 채우는 규칙을 살펴보면 대각선 왼쪽 아래, 가로, 대각선 왼쪽 위 방향으로 반복하며 총 n회 실시한다

삼각형의 각 칸을 좌표로 표현하면 아래와 같이 나타낼 수 있다

[0, 0]	[0, 1]	[0, 2]	[0, 3]
[1, 0]	[1, 1]	[1, 2]	[1, 3]
[2, 0]	[2, 1]	[2, 2]	[2, 3]
[3, 0]	[3, 1]	[3, 2]	[3, 3]

 

삼각형을 채우는 규칙과 각 칸의 좌표들을 함께 살펴보면 다음과 같다

• 대각선 아래로 이동할 때는 x좌표가 증가
• 가로로 이동할 때는 y좌표가 증가
• 대각선 위로 이동할 때는 x,y좌표가 감소

 

이 규칙을 이용하여 삼각형의 좌표에 해당하는 값을 저장할 [n][n]크기의 배열을 선언하고 [0, 0] 좌표부터 달팽이 채우기한 값을 넣어준다

int[][] tri = new int[n][n];

int x = -1; // x 좌표
int y = 0; // y 좌표
int num = 1; // 달팽이 채우기 값
		
for(int i = 0; i < n; i++) {
	for(int j = i; j < n; j++) {
		if(i % 3 == 0) { // 대각선 아래
			x++;
		}
		else if(i % 3 == 1) { // 가로
			y++;
		}
		else if(i % 3 == 2) { // 대각선 위
			x--;
			y--;
		}
		tri[x][y] = num++;
	}
}

 

마지막으로 정답을 반환할 배열을 만들고 삼각형의 윗줄의 값부터 차례대로 넣어준다
이때 삼각형 칸의 값이 0인 경우에는 삼각형에 포함되는 범위가 아니기 때문에 제외한다

int[] answer = new int[n*(n+1) / 2]; // 삼각형의 크기 ( 1 ~ n 까지 합)

int index = 0;
for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
		if(tri[i][j] == 0) break;
		answer[index++] = tri[i][j];
	}
}
       
return answer;

 

최종 코드

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[n*(n+1) / 2]; // 삼각형의 크기 ( 1 ~ n 까지 합)
		int[][] tri = new int[n][n];
		
		int x = -1; // x 좌표
		int y = 0; // y 좌표
		int num = 1; // 달팽이 채우기 값
		
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(i % 3 == 0) { // 대각선 아래
					x++;
				}
				else if(i % 3 == 1) { // 가로
					y++;
				}
				else if(i % 3 == 2) { // 대각선 위
					x--;
					y--;
				}
				tri[x][y] = num++;
			}
		}
		
		int index = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(tri[i][j] == 0) break;
				answer[index++] = tri[i][j];
			}
		}
        
        return answer;
    }
}

---