[프로그래머스 - Java] 삼각 달팽이

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

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

 

풀이

 

삼각 달팽이 문제는 규칙을 찾는것이 가장 어려웠다.

 

이 문제를 푸는데 가장 중요한 아이디어는

정삼각형 형태인 주어진 수들을 왼쪽으로 몰아 2차원배열에 직각삼각형 형태로 놓는다고 생각하는 것이다.

이렇게 생각을 바꾸고 나면 쉽게 풀이가 가능하게 된다.

 

1. 적히는 숫자들의 총 갯수는 n*(n+1)/2 (등차수열의 합)이므로 answer배열의 크기를 n*(n+1)/2로 설정해 준다.
2. 직각삼각형 형태로 수를 저장할 n*n의 2차원 배열을 하나 생성하고 여기에 해당하는 숫자들을 넣는 코드를 구현해야한다.
   1. 위의 그림에서 알 수 있듯이 1 ~ n*(n+1)/2의 수는 아래방향, 오른쪽방향, 위쪽대각선방향의 순서를 반복하며 적히게 된다.
   2. 이 때 방향이 달라질 때 마다 n개, n-1개, n-2개,...,1개의 수가 적히게 된다.
   3. 아래 방향 : r++ / 오른쪽 방향 : c++ / 대각선 위 방향 : r--, c--
   4. 위와 같이 적히는 좌표가 달라지게 되므로 적히는 수의 개수와 방향에 맞게 for문을 구현한다. (코드 참조)
   5. 방향이 달라질 때 마다 n을 1씩 감소시키고 n이 0이되면 수행을 종료한다.
3. 2차원배열을 모두 채운 뒤에는 이를 1차원 배열인 answer에 해당하는 인덱스에 맞게 넣어줘야한다.
   1. 2차원배열을 왼쪽 위부터 차례로 탐색하며 0이 아닌 값이 담겨있는 경우만 answer에 넣어주면 된다.

 

class Solution {
    public int[] solution(int n) {
        int size = (n+1)*n/2;
        
        int[] answer = new int[size];
        int[][] temp = new int[n][n];
        int num = 1;
        int r = -1;
        int c = 0;
        
        size = n;
        while(n>0){
            //아래 대각선
            for(int i=0; i<n; i++){
                r++;
                temp[r][c] = num;
                num++;
                
            }
            
            n--;
            if(n==0)
                break;

            //오른쪽
            for(int i=0; i<n; i++){
                c++;
                temp[r][c] = num;
                num++;
            }
            n--;
            if(n==0)
                break;
            
            //위로 대각선
            for(int i=0; i<n; i++){
                r--;
                c--;
                temp[r][c] = num;
                num++;
            }
            n--;
            if(n==0)
                break;
        }
        
        //temp값을 answer에 옮기기
        int idx = 0;
        for(int i=0; i<size; i++) {
			for(int j=0; j<size; j++) {
				if(temp[i][j] == 0) {
					break;
				}
				answer[idx] = temp[i][j];
				idx ++;
			}
		}
            
        return answer;
    }
}