[코딩테스트][Java] 프로그래머스 68645, 삼각달팽이

본 풀이는 공부 목적으로 다른 사람의 풀이인 nimkoes , k-BonnieHan , 코자바님의 풀이를 디버그한 것을 정리한 글입니다.

 

문제

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

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

 

접근방법

N*N 배열에서 수들이 채워지는 방향은 다음과 같이 총 3가지이고 Down->Right->Up & Left 순서로 반복적으로 채워집니다.

• Down
• Right
• Up & Left

예를 들어 N=4일때의 수가 채워지는 순서는 아래 그림과 같습니다.

위의 그림을 보면 수들이 처음에는 Down 방향으로 채워지다가 Right 방향으로 채워지고 Up 방향으로 채워지는 것을 볼 수 있습니다. 그리고 Up & Left 방향 다음에는 다시 Down 방향으로 채워지는 것을 볼 수 있습니다.

 

위 그림에서 수들은 2차원 배열에서 계단식으로 채워지는 것을 볼 수 있습니다. 이를 코드로 표현하면 다음과 같습니다.

for(int i=0; i<n; i++)
{
	for(int j=i; j<n; j++)
	{
		matrix[j][i] = num++;
	}
}

위와 같은 코드를 수행하면 아래와 같은 결과가 나올 것입니다.

하지만 달팽이 모양으로 채우기 위해서는 방향이 DOWN->RIGHT->UP & LEFT의 방향으로 움직여야 하기 때문에 반복문의 인덱스를 matrix의 인덱스로 사용하지 않고 방향을 위한 인덱스로 사용합니다. 반복문 변수 i의 기능은 다음과 같습니다.

• i==0 or i==3 : DOWN
• i==1 : RIGHT
• i==2 : UP & LEFT

 

matrix의 인덱스로 사용하는 변수는 x,y를 사용합니다. x는 행, y는 열을 의미합니다. 방향에 따른 x와 y의 변화는 다음과 같습니다.

• DOWN : x=x+1
• RIGHT : y=y+1
• UP & LEFT : x=x-1, y=y-1

즉 위의 조건을 정리하면 다음과 같습니다.

if(i%3==0)	// down
{
	x++;
}
else if(i%3==1)	// right
{
	y++;
}
else if(i%3==2)	// up & left
{
	x--;
    y--;
}

위의 코드에서 나머지 3연산을 하는 이유는 방향의 단계가 총 3단계이기 때문입니다.

 

위 코드를 정리하면 다음과 같습니다.

        int x = -1, y = 0;	// x:row y:col
        int num = 1;

        
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                if (i % 3 == 0) {	// down
                    ++x;
                } else if (i % 3 == 1) {	// right
                    ++y;
                } else if (i % 3 == 2) {	// up & left 
                    --x;
                    --y;
                }
                matrix[x][y] = num++;
            }
        }

 

디버그 결과는 다음과 같습니다.

 

Java 언어 기반 소스코드

import java.util.Arrays;

public class Solution2 {
    public int[] solution(int n) {
    	// a_n = a1(1) + (n^2+n-2)/2
    	//	  = 2/2 + (n^2+n-2)/2
    	//    = (n^2+n)/2
    	//    = (n(n+1))/2
        int[] answer = new int[(n*(n+1))/2];
        int[][] matrix = new int[n][n];

        int x = -1, y = 0;	// x:row y:col
        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;
    }
    
    public static void main(String[] args)
    {
    	for(int i=1;i<=6;i++)
    	{
    		System.out.println(Arrays.toString(new Solution2().solution(i)));
    	}
    }
}

 

References

https://programmers.co.kr/learn/courses/30/lessons/68645
nimkoes , k-BonnieHan , 코자바님 풀이