[programmers] 삼각 달팽이

https://school.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. 반환할 answer 배열의 크기를 등차수열의 합만큼 생성합니다. 이는 필요한 요소의 총개수를 의미합니다. 

2. 피라미드 형태가 아닌 2차원 배열 arr에 값을 채워두고, 이를 나중에 answer로 이동할 것이므로 arr을 생성합니다.

3. 2중 for문을 돌면서 아래 ➡ 오른쪽 ➡ 대각선으로 이동을 반복할 것입니다.  if-else if문을 활용해서 3방향으로 반복적으로 이동 (i%3 ==  0, i%3 ==  1, i%3 ==  2)합니다.

- 아래로 이동(i%3 == 0): x 좌표 1 증가, y는 그대로 유지합니다. 
- 오른쪽으로 이동(i%3 == 1): y 좌표 1 증가, x는 그대로 유지합니다.
- 대각선으로 이동(i%3 == 2): x 좌표와 y 좌표를 동시에 1씩 감소시킵니다. 

4. arr 원소를 answer로 이동하여 반환합니다.

코드 구현

실패 코드

class Solution {
   public int[] solution(int n) {
        int x = 0;
        int y = 0;
        int num = 1;
        
        // 등차수열의 합만큼 배열 크기 생성
        int[] answer = new int[n*(n+1)/2];
        // 2차원 배열 생성
        int[][] arr = new int[n][n];
        
        // 2중 for문 돌기) 아래 -> 오른쪽 -> 대각선 반복
        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{
                    // 대각선
                    x--;
                    y--;
                }
                arr[x][y] = num++;
            }
        }

        // arr[x][y] 원소 -> answer 배열로 이동
        int k = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                answer[k++] = arr[i][j];
            }
        }

        return answer;
    }
}

 

원인 및 해결

1. 초기 위치 설정 오류

x, y의 위치를 (0,0)으로 초기화하는 게 맞으나, 현재 코드상으로 볼 때 첫 번째 숫자를 넣기 전에 for문의 첫 번째 반복에서 바로 x++ 또는 y++를 수행합니다. 즉, 첫 번째 숫자를 넣기도 전에 위치 변경이 일어나고 있습니다. 따라서 실제로 첫 번째 숫자가 (0,0)에 들어가지 않고 (1,0)에 첫 번째 숫자가 들어가기 때문에 x = -1로 수정합니다.

그럼 y를 조정하지 않은 이유는 무엇일까요?
이동 패턴 때문입니다. 이 문제에서는 아래 ➡ 오른쪽 ➡ 대각선으로 이동하므로 처음 아래로 이동 시 x좌표만 증가하고 y좌표는 변하지 않습니다. 따라서 y좌표는 변경할 필요가 없습니다. 

 

2. 배열의 요소를 answer 배열로 옮기는 부분의 오류

for(int j=0; j<i; j++)가 아니라 for(int j=0; j<=i; j++)로 수정해야 합니다. 현재 조건으로는 각 행의 마지막 요소가 누락됩니다.

 

성공 코드

class Solution {
    public int[] solution(int n) {
        int x = -1;
        int y = 0;
        int num = 1;
        // 등차수열의 합만큼 배열 크기 생성
        int[] answer = new int[n*(n+1)/2];
        // 2차원 배열 생성
        int[][] arr = new int[n][n];
        
        // 2중 for문 돌기) 아래 -> 오른쪽 -> 대각선 반복
        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{
                    // 대각선
                    x--;
                    y--;
                }
                arr[x][y] = num++;
            }
        }

        // arr[x][y] 원소 -> answer 배열로 이동
        int k = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                answer[k++] = arr[i][j];
            }
        }

        return answer;
    }
}

 

배우게 된 점

1. 등차수열의 합

 

2. 숫자들이 특정 이동 방향으로 반복적으로 채워질 때 (feat. i%3 == 0, i%3 == 1...로 조건을 분기하는 이유)

- 아래로 이동 (i%3 == 0):  x (행의 인덱스)는 증가하지만, y (열의 인덱스)는 변하지 않습니다.

- 오른쪽으로 이동 (i%3 == 1): y는 증가하지만, x는 변하지 않습니다.

- 대각선 위로 이동 (i%3 == 2): x와 y 모두 감소합니다.