[Lv.2] 프로그래머스 - 삼각 달팽이 : Java

프로그래머스

 

 

 

 

이해하기

삼각 달팽이 문제를 이미 한 번 풀어본 적이 있지만 (사실상 풀이 참고 & 스터디원분의 설명 듣기)

기억나는 것이라고는 '이런 문제가 나오면 일단 왼쪽으로 싹 밀어보세요!' 라는 스터디원분의 설명뿐...^^

이거라도 기억나는게 어디야 하고 일단 다 밀어봤다.

 

위처럼 정리한 후, 방향은 세 가지라는 것까지 생각했다. (아래쪽, 오른쪽, 왼쪽 위 대각선)

그리고 예시로 나온 n = 4, n= 5, n = 6  삼각형을 그려보며 맨 마지막에 각각 10, 15, 21이 오게 된 이유에 대해 생각해보았다.

다른 블로그 글을 보니 등차수열? 이라는데 거기까지 생각하지는 못했고, 단지 n과 n + 1을 곱해서 2로 나누면 각각의 마지막 값이 나오는구나! 까지 알아냈다.

 

간단한 공식도 잘 기억나지 않는다...^^

 

참고한 블로그⬇️

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

 

 

n = 4일 때 숫자가 채워지는 순서는 위 그림과 같다.

먼저 아래쪽 (빨간색) 으로 1씩 늘어난 숫자가 채워진다. 이는 x값이 +1 된 것이라 볼 수 있다.

다음으로 오른쪽 (초록색) 으로 1씩 늘어난 숫자가 채워진다. 이는 y값이 +1 된 것이라 볼 수 있다.

다음으로 왼쪽 위 대각선 (파란색) 으로 1씩 늘어난 숫자가 채워진다. 이는 x값이 -1, y값이 -1 된 것이라 볼 수 있다.

마지막으로 아래쪽 (보라색) 으로 1씩 늘어난 숫자가 채워진다. 이는 마찬가지로 x값이 +1 된 것이라 볼 수 있다.

 

 

문제풀이

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(n * (n + 1)) / 2];
        int[][] matrix = new int[n][n];
        
        int x = -1;
        int y = 0;
        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 {                    // 대각선 왼쪽 위
                    x--;
                    y--;
                }
                
                matrix[x][y] = num++;
            }
        }
        
        int k = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    break;
                } else {
                    answer[k++] = matrix[i][j];
                }
            }
        }
        
        return answer;
    }
}

 

        int[] answer = new int[(n * (n + 1)) / 2];
        int[][] matrix = new int[n][n];

 

위에서 구했던 max = (n * (n + 1)) / 2 를 사용하여 answer 배열의 크기를 잡는다.

matrix는 n x n 크기로 잡는다.

 

        int x = -1;
        int y = 0;
        int num = 1;

 

x 좌표는 -1, y 좌표는 0,  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 {                    // 대각선 왼쪽 위
                    x--;
                    y--;
                }
                
                matrix[x][y] = num++;
            }
        }

 

이중 for문을 돌면서 matrix 배열을 채워간다.

n = 4를 예시로 들면 다음과 같다.

 

        int k = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    break;
                } else {
                    answer[k++] = matrix[i][j];
                }
            }
        }

 

k는 인덱스를 나타내기 위한 변수이다.

이중 for문을 돌면서 matrix[i][j] 의 값이 0이라면 break하고, 그렇지 않다면 answer[k++]에 해당 matrix[i][j]의 값을 넣어준다.