[프로그래머스/JAVA] 삼각 달팽이

문제 링크

https://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. 정답 배열의 크기는 1부터 n까지 더한 값만큼의 크기이므로 n*(n+1)/2 크기로 선언해 주었습니다.
  2. 1부터 n까지의 크기를 가지는 이차원 배열을 생성해 주었습니다.
  3. 방향을 바꿀 기준을 잡아주었습니다.

  4. 값이 n*(n+1)/2이 되면 반복문을 종료합니다.

  5. 정답 배열에 이차원 배열을 차례대로 입력합니다.

 

풀이

class Solution {
    int dx[] = {1,0,-1};
    int dy[] = {0,1,-1};
    public int[] solution(int n) {
        int[] answer = new int[n*(n+1)/2];
        int[][] arr = new int[n][];
        for (int i = 0; i < arr.length; i++) {
		    arr[i] = new int[i+1];
	    }

        int num =1;
        int x=-1;
        int y=0;
        int way=0;
        while(true) {
        	int nextX = x+dx[way%3];
        	int nextY = y+dy[way%3];
            
            if(num == n*(n+1)/2+1) break;
        	if(!isRange(n, nextX, nextY,arr)) {
        		way++;
        		continue;
        	}
        	arr[nextX][nextY] =num++;
        	x= nextX;
        	y= nextY;

        }
        int i=0;
        for(int[] array: arr) {
        	for(int val: array) {
        		answer[i++] = val;
        	}
        }

        return answer;
    }

    public boolean isRange(int n , int x, int y,int[][]arr) {
	    if(x<0 || y <0 || x>=n || y > x ||arr[x][y]!=0) return false;
	    return true;
    }
}