[프로그래머스 Level.2] 삼각 달팽이 (월간 코드 챌린지 시즌1) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 월간 코드 챌린지 시즌1 > 삼각 달팽이

 

 

문제 설명

 

 

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

 

• 문제 예시와 같습니다.

 

 

 

 

나의 코드

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[n*(n+1)/2];
        int[][] block = new int[n][n];
        
        int x = 0;
        int y = -1; // (0,-1)이 시작지점이라 치고 (0,0)에 1을 넣는 것부터가 첫번째
        int num = 1;
        
        // ((왼쪽 위 시작) - 아래 - 오른쪽 - 왼쪽 대각선 위) 방향 3가지 동작으로 순차적으로 진행
        // 아래로 n번 -> 오른쪽으로 n-1번 -> 대각선으로 n-2번 ... -> ~방향으로 1번 순으로 n에서 1씩 감소
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {
                if(i % 3 == 0) { // 아래
                    y++;
                } else if(i % 3 == 1) { // 오른쪽
                    x++;
                } else { // 왼쪽 대각선 위
                    x--;
                    y--;
                }
                block[y][x] = num++;
            }
        }
        
        int idx = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(block[i][j] == 0) 
                    break;
                answer[idx++] = block[i][j]; 
            }
        }
        
        return answer;
    }
}

 

풀이

1. 규칙을 찾아서 푸는 문제로 블록의 숫자를 보면 아래로 갔다가 -> 오른쪽으로 갔다가 -> 위로 가는 것을 볼 수 있다.
2. 왼쪽 제일 첫 번째 블록들을 1열로 보면 왼쪽 맨위가 제일 높은 계단 형식으로 블록을 쌓이는 것으로 볼 수 있다.
3. 그러면 방향과 숫자의 블록을 따져보면 1번 블록을 (0, 0)으로 놓고 첫 번째 루틴대로 블록을 놓는다면 다음과 같다.
   (1) (0, 0)부터 (0, n-1)까지 아래로 행이 증가하면서 n번 블록을 놓는다.
   (2) (0, n-1)은 블록이 놓여있으니 (1, n-1)부터 (n-1, n-1)까지 오른쪽으로 열이 증가하면서 (n-1)번 블록을 놓는다.
   (3) (n-1, n-1)은 블록이 놓여있으니 (n-2, n-2)부터 (1, 1)까지 왼쪽 대각선 위로 행과 열이 감소하면서 (n-2)번 블록을 놓는다.
4. 이렇게 블록이 쌓이는 것을 봤을 때 좌표를 (y, x)로 봤을 때 (0, -1)부터 시작해서 첫 번째 블록을 (0, 0)에 놓는 것을 시작으로 y가 증가하면서 아래로 n번 블록을 놓고 x가 증가하면서 오른쪽으로 (n-1)번 블록을 놓고 y와 x가 감소하면서 왼쪽 대각선으로 (n-2)번 놓고 다시 아래로 (n-3)번 다시 오른쪽으로 (n-4)번 다시 왼쪽 대각선 위로 (n-5)번 ... ~로 1번 이렇게 반복하는 것을 알 수 있다.
5. 1부터 n까지의 합이 블록의 총 개수이므로 1~n까지의 합 공식 n(n+1)/2 을 이용하여 answer 배열의 크기를 정한다.
6. 그리고 블록을 놓기 위한 int형 2차원 배열을 생성하고 좌표를 나타낼 int형 변수 x와 y를 (0, -1)로 초기화한다.
7. 이중 for문을 사용하여 블록을 놓기 시작한다.
   바깥 for문은 ~방향으로 n번~1번까지이므로 n번 반복하고, 내부 for문은 처음엔 n번 부터 1씩 감소하여 실행되야 하므로 i부터 시작해서 n-1까지 실행되도록 한다.
8. 그리고 세 가지 동작이 순차적으로 반복하여 실행되므로 (i % 3)의 값에 따라 각각 y 1씩 증가, x 1씩 증가, y와 x 1씩 감소하도록 하며 해당 좌표에 블록의 숫자를 증가시키며 놓는다.
9. 이렇게 모든 블록을 다 놓게 되면 배열 원소의 값이 0이 아닌 것들만 블록을 놓은 것이므로 다시 배열을 이중 for문을 돌면서 값이 0이 아닐 때만 배열의 값을 answer의 인덱스 0부터 순서대로 담는다.