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

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

728x90

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; } }

728x90

from http://hyojun.tistory.com/32 by ccl(A) rewrite - 2021-12-10 14:02:12