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

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

프로그래머스

삼각 달팽이 문제

달팽이 형태로 그리면서 채울 때 배열 순서대로 반환하는 문제

 

#사용 알고리즘

구현

📌문제 접근 포인트

1. 사각이 아닌 삼각으로 움직이는 달팽이의 모습을 생각해야한다. n의 갯수는 1부터 n까지의 합만큼만 달팽이가 움직이는걸 예시를 통해 확인할 수 있다.

2. 달팽이의 움직이는 모양을 생각해보자. 삼각형이므로 ↙→↖ 이렇게 3 방향으로 움직이는거로 보이지만, 우리가 배열로 생성할 때는 ↙ → ↑ 형태로 움직인다는 것을 생각해야한다. ↙→↖의 형태로 움직이면 배열 상으로 만나지 않게 된다.

3. 배열의 크기를 만들어서 우측 상단부터 시작해서 해당 조건으로 움직이는 형태의 달팽이를 구현하면 성공

그림으로 보는 요약

반응형

⚙ 내가 푼 정답 코드

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[(n*(n+1))/2];
        int[][] snail = new int[n][n];
        int[] dy = {1, 0, -1};
        int[] dx = {-1, 1, 0};
        int d = 0;
        int y = 0;
        int x = n-1;
        
        for (int i = 1; i < (n*(n+1))/2+1; i++){
            snail[y][x] = i;
            int ny = y + dy[d];
            int nx = x + dx[d];
            if (ny >= 0 && ny < n && nx >= 0 && nx < n && snail[ny][nx] == 0){
                y = ny;
                x = nx;
                
            }
            else{
                d = (d+1)%3;
                y = y + dy[d];
                x = x + dx[d];
            }
        }
        int index = 0;
        for (int i = 0 ; i < n; i++){
            for (int j = 0 ; j<n; j++){
                if (snail[i][j] != 0){
                    answer[index++] = snail[i][j];
                }
            }
        }
        
        return answer;
    }
}