[PS/JAVA] (배열/수학) 프로그래머스_68645_삼각 달팽이

문제 

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

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 문제 예시와 같습니다.

 

 

---

문제에서 인사이트 도출

 

1. 문제 파악

 

• N이 주어지면, N을 이용하여 삼각형 형태로 상단 좌우부터 차례로 1씩 증가하는 수를 넣어 피라미드 삼각형 만들기
• 삼각형 전체의 밑변과 높이는 N과 정비례, 밑변과 높이는 같음.
• x번째의 층에는 x개의 숫자가 들어감 (1 <= x <= N)
• 2차원 배열 형태의 피라미드를 구현한 후, 수를 차례로 세어나가는 방식을 사용해야 할 듯.

 

2. 제한사항 파악

N은 1 이상, 1000 이하의 자연수. -> O(N^3) 이상의 시간 복잡도. 3중 반복문(N만큼을 반복하는) 등을 사용하게 되면 시간초과의 위험이 있음.

 

 

 

---

풀이과정 도출

 

1. 수학으로 풀이?

2차원 배열의 각 원소들에 대해서 분명히 어떤 수학적 규칙이 있을 것으로 예상됨. 하지만 해당 수식을 도출해내는 과정을 위해서 통상적으로 생각하기 매우 복잡한 면이 있음. 따라서 수학적으로 각 인덱스에 따른 수식을 도출하여 들어갈 수를 직접 계산해 내는 방법은 사용하기 매우 어려울 것으로 생각함.

 

2. 직접 그려본다.

따라서 문제에 제시된 규칙대로 직접 그려보는 방법이 가장 현실적이고 빠른 시간 내에 문제를 풀이할 수 있을 것이다. 직접 그려보는 방법은 O(N^3) 이상의 복잡한 알고리즘을 사용하지 않을 것으로 예상된다.

 

2-1. 피라미드 -> 직각 삼각형으로 바꾸어 생각하기

 

피라미드를 다르게 생각하면 다음과 같이 직각 삼각형 형태로 변환할 수 있다. 따라서 이를 2차원 배열 형태로 표현하기 용이할 것이다.

우선 맨 처음 N*N의 배열을 생성한 후 모든 원소를 0으로 초기화한 이후, 삼각형을 차례로 채워나가면 된다.

 

 

2-2.  총 반복횟수 구하기

숫자의 최댓값은 (((n * n) - n) / 2 ) + n이다. 위의 예시로 계산해보면 (((4 * 4) - 4) / 2) + 4 = 10이다.

반복횟수 또한 이와 같으므로 해당 수만큼 반복하면 된다.

 

2-3.  방향과 방향전환 조건

방향은 [하향] -> [우향] -> [대각 좌상향] 세 가지를 반복한다. 

현재 좌표를 matrix[y][x] 라고 했을 때, 방향 전환 조건은 

 

1. 하향 -> 우향

• 진행 방향에 이미 숫자가 채워짐 : matrix[y + 1][x]이 0이 아님
• 삼각형의 최대 크기를 초과함 : y+1이 n일 경우

 

2. 우향 -> 대각 좌상향

• 진행 방향에 이미 숫자가 채워짐 : matrix[y][x + 1]이 0이 아님
• 삼각형의 최대 크기를 초과함 : x+1이 n일 경우

 

3. 대각 좌상향 -> 하향

• 진행 방향에 이미 숫자가 채워짐 : matrix[y - 1][x - 1]이 0이 아님
• 삼각형의 최대 크기를 초과함 : x - 1이 0일 경우 (x-1 == 0이면, y-1은 자동으로 0이다.)

 

 

---

문제풀이

 

 

1. 직각 삼각형을 담을 배열 초기화, 총 반복횟수 구하기

 

import java.util.*;
class Solution {
    public int[] solution(int n) {
        int[][] array = new int[n][n];
        for(int[] row: array){
            Arrays.fill(row, 0);
        }

        int length = (((n * n) - n) / 2) + n;
    }
}

 

•  N*N의 배열을 생성한 후 모든 원소를 0으로 초기화
• 숫자의 최댓값은 (((n * n) - n) / 2 ) + n번

 

 

2. 삼각형을 채우는 것을 반복

import java.util.*;
class Solution {
    public int[] solution(int n) {
        int[][] array = new int[n][n];
        for(int[] row: array){
            Arrays.fill(row, 0);
        }

        int length = (((n * n) - n) / 2) + n;
        
        char action = 'v'; //v, h, d, 아래, 오른쪽, 왼쪽위 대각
        int x = 0;
        int y = -1;
        for(int i = 1; i <= length; i++){
            if(action == 'v'){
                y++;
                if((y + 1 >= n || array[y+1][x] != 0)){
                    action = 'h';
                }
            }
            else if(action == 'h'){
                x++;
                if((x + 1 >= n || array[y][x+1] != 0)){
                    action = 'd';
                }
            }
            else{
                x--;
                y--;
                if((x - 1 <= 0 || array[y-1][x-1] != 0)){
                    action = 'v';
                }
            }
            array[y][x] = i;
        }
    }
}

• 진행방향에 대한 변수로 action을 선언하였다. 첫 행동은 아래로 진행되어야 하므로 action을 'v'로 초기화하였다.
• 첫 시작점은 (0,0)의 바로 위인 (0,-1)로 잡았다. 왜냐하면 아래의 반복문에서 이동을 먼저 한 후, 배열에 값을 채우기 때문이다.
• 1에서부터 최댓값까지 반복문을 돌리며, 진행방향에 따라 이동 후 숫자를 채운다. 만약 방향 전환이 필요하다면 다음 진행방향 변수 action을 변경하여 다음 반복문 실행 시, 반영되도록 한다.
• 각각의 방향으로 진행할 때 인덱스는 하향 시 [y++], 우향시 [x++], 대각 좌상향시 [x-- / y--] 가 이루어지면 된다.
• 방향 전환 조건은 위에서 언급했던 아래의 사항이다.

현재 좌표를 matrix[y][x] 라고 했을 때, 

1. 하향 -> 우향

• 진행 방향에 이미 숫자가 채워짐 : matrix[y + 1][x]이 0이 아님
• 삼각형의 최대 크기를 초과함 : y+1이 n일 경우

2. 우향 -> 대각 좌상향

• 진행 방향에 이미 숫자가 채워짐 : matrix[y][x + 1]이 0이 아님
• 삼각형의 최대 크기를 초과함 : x+1이 n일 경우

3. 대각 좌상향 -> 하향

• 진행 방향에 이미 숫자가 채워짐 : matrix[y - 1][x - 1]이 0이 아님
• 삼각형의 최대 크기를 초과함 : x - 1이 0일 경우 (x-1 == 0이면, y-1은 자동으로 0이다.)

 

 

 

 

3. 출력을 위해 상단 좌측부터 숫자를 차례로 1차원 배열로 이동시킨다.

import java.util.*;
class Solution {
    public int[] solution(int n) {
        int[][] array = new int[n][n];
        for(int[] row: array){
            Arrays.fill(row, 0);
        }

        int length = (((n * n) - n) / 2) + n;
        char action = 'v'; //v, h, d, 아래, 오른쪽, 왼쪽위 대각
        int x = 0;
        int y = -1;
        for(int i = 1; i <= length; i++){
            if(action == 'v'){
                y++;
                if((y + 1 >= n || array[y+1][x] != 0)){
                    action = 'h';
                }
            }
            else if(action == 'h'){
                x++;
                if((x + 1 >= n || array[y][x+1] != 0)){
                    action = 'd';
                }
            }
            else{
                x--;
                y--;
                if((x - 1 <= 0 || array[y-1][x-1] != 0)){
                    action = 'v';
                }
            }
            array[y][x] = i;
        }

        int[] answer = new int[length];

        int index = 0;
        for(int i = 0; i < array.length; i++) {
            for (int j = 0; j < i + 1; j++) {
                answer[index] = array[i][j];
                index++;
            }
        }


        return answer;
    }
}

• 출력 형식이 1차원 배열 형식이므로, 2차원 배열의 상단 좌측부터 1차원 배열에 차례로 넣으면 된다.
• 2차원 배열의 각 행은 행 번호만큼만 열을 출력하면 된다. -> 2행이 가진 열은 2개, 3행이 가진 열은 3개
• 따라서 0 ~ 행 인덱스만큼 내부 반복문을 돌린다.