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

문제

programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

설명

* Jungol 1337 달팽이 삼각형 문제랑 같다. 삼각형 그리는 방식이 살짝 다르지만

 

코드 챌린지 할 때도 뭔가 이거 규칙이 있는 거 같은데...? 하면서도

뭐지!!!!!! 이러다가 결국 달팽이 삼각형 문제의 정답을 보고 말았다ㅠ_ㅠ

근데도 뭔가 이해가 될락말락해서 정리를 해본다!

 

 

• n은 1 이상 1,000 이하입니다.

 

 

n이 1일 때부터 6일때 까지의 삼각 달팽이를 만들면 위의 그림과 같다.

 

코드로 저 삼각형을 나타내야하는데...? 저걸 뭐 트리로 나타내야 하나 ㅇㅂㅇ 싶기도 하지만

그냥 쉽게 왼쪽으로 싹 밀어버리면 생각하는게 쉬워진다!

 

 

 

이렇듯 n * n 배열로 삼각형을 표현할 수 있다!

 

그리고 각 숫자는 반시계 방향으로 달팽이 채우기를 하는데 규칙이 있다.

 

 

 

아래 - 오른쪽 - 대각선의 순서가 반복되며 채워지는 것이다!

 

그리고 아래 - 오른쪽 - 대각선의 순서마다 n만큼 - n-1만큼 -... - 2만큼 - 1만큼 이렇게 숫자가 1 만큼씩 떨어지면서 채워진다.

 

이를 수식으로 나타내면 n만큼의 달팽이 채우기를 했을 때, 몇 번 숫자에서 채우기가 끝나는지 알 수 있다.

이 끝나는 숫자를 안다면 정답을 담아낼 answer 배열을 얼만큼 초기화할지 알 수 있다.

 

(TMI 1 : 굳이 이렇게 안 구해도 되는데 뭔가 규칙이 있어서 한 번 구해봤다...

그리고 이걸 구하면서 중학교땐가...? 배운 수학의 개념에 대해서도 다시 한번 정리하는 시간을 가졌다^^;; 기억 안 나 ㅎ)

(TMI 2 : 이렇게 안 구하면 그냥 이차원 배열을 싹 다 출력하면서 0이 아닌 숫자 값이 들어간 방의 값들만 빼서 그걸 바탕으로 answer 배열을 구성해도 된다.)

 

 

 

 

등차수열... 공차... 어디서 많이 들어봤다^_______^!

 

max값은 n값에 따른 마지막으로 채워지는 번호이다.

그리고 이 max값은 1부터 n까지의 합이다.

 

그렇다면 answer 배열은 등차수열 합의 일반항 공식에 따라 아래와 같이 표현된다.

 

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

 

자 그럼 본격적으로 이차원 배열에서 달팽이 채우기를 해보자!

n=4일 때는 아래와 같이 채워진다.

 

 

 

이차원 배열을 이중 for문 반복문을 통해 돌면서 우리가 원하는 (x, y) 좌표에 숫자들을 넣어야 한다.

 

 

 

좌표가 움직이는 순서를 보면 위의 설명과 같은 순서로 움직인다.

이에는 규칙이 있다.

 

 

 

 

이중 for문으로 이차원 배열을 순회하지만 j가 원래 우리가 알던 0이 아닌 i부터 시작한다.

왜냐하면 아래 - 오른쪽 - 대각선 반복이 될 때마다 숫자가 1씩 감소하기 때문이다.

 

그리고 아래로 갈 때는 x좌표 값을 1 증가해주면 되고

오른쪽으로 갈때는 y좌표 값을 1 증가

대각선으로 갈때는 x좌표, y좌표 둘 다 1씩 감소시켜주면 우리가 원하는 삼각 달팽이 채우기를 할 수 있는 것이다!

 

(교훈 : 뭔가 장황하게 설명을 한 거 같은데 정말 규칙도 잘 찾아야 하고 이를 코드로도 잘 나타낼 수 있도록 공부를 많이 해야겠다..!)

코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(n*(n+1))/2];
        int[][] matrix = new int[n][n];

        int x = -1, 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 if (i % 3 == 2) {
                    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;
                answer[k++] = matrix[i][j];
            }
        }

        return answer;
    }
}

GITHUB

github.com/KwonMinha/Programmers/blob/master/CodeChallenge/src/SnailTriangle.java

KwonMinha/Programmers