삼각 달팽이(프로그래머스) JAVA

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

프로그래머스

 

문제 설명

이렇게 삼각형으로 된 피라미드 모양이 있을 때, 순서대로 움직이면서 일차원 배열에 숫자를 집어넣습니다.

아래로, 오른쪽으로, 대각선 위 순서로 움직입니다.

이 순서로 움직이면 

이런 1차원 배열이 나옵니다.

 

문제에 대한 아이디어

간단하게 생각해 보면 아래 방향으로 움직이고 오른쪽으로 가고 그다음 대각선 위로 가면 됩니다.

2차원 배열을 하나 만들어 절반만 사용해서 문제를 해결하면 쉽게 풀 수 있을 것 같습니다.

제가 생각한 코드는 각각 방향으로 움직이는 for문 3개를 만들어 움직이는 것이었습니다.  

분명 이렇게 풀어도 풀리지만 가독성면에서 너무 안 좋을 것 같아서 다른 방법으로 풀 수 있나  생각해 봤습니다.

 

책에서 dx,dy로 방향을 정해서 풀기를 배웠습니다. 즉 변화량으로 특정 방향으로 이동할 때 해당 좌표 값이 어떻게 변화하는지를 의미합니다. 이런 방법은 DFS, BFS에서도 많이 사용합니다.

 

전체 코드

class Solution {
    //이 배열은 변하지 않으므로 static fianl 값으로 선언합니다.
    private static final int[] dx = {0, 1, -1};
    private static final int[] dy = {1, 0, -1};
    
    public int[] solution(int n) {
        int pro[][] = new int[n][n];
        int now =1;
        int y = 0;
        int x = 0;
        int d = 0;
        
        while(true){
            pro[y][x] = now;
            ++now;
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(nx == n || ny == n || nx == -1 || ny == -1 || pro[ny][nx] != 0){
                d = (d+1)%3;
                nx = x + dx[d];
                ny = y + dy[d];
                if(nx == n || ny == n || nx == -1 || ny == -1 || pro[ny][nx] != 0) break;
            }
            x = nx;
            y = ny;
        }

        int[] answer = new int[now-1];
        int idx = 0;
        for(int i = 0; i< n; ++i){
            for(int j = 0; j <= i; ++j){
                answer[idx] = pro[i][j];
                ++idx;
            }
        }
        return answer;
    }
}

• dx, dy는 방향을 움직일 때 자주 쓰는 방법입니다.
• 여기서는 아래, 오른쪽, 대각선 3개의 방향을 설정했습니다.
• 방향을 변경하고 그 다음 위치도 꽉 차있는지 체크해야합니다.