(알고리즘 스터디) 10주차 월_(Programmers) 삼각 달팽이

🌟 프로그래머스 / 월간 코드 챌린지 시즌 1 / Level 2 / 삼각 달팽이

📃 문제

프로그래머스

🚫 제한 사항

• 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️⃣ 좌표화

➡️ 이 문제에서 중요한 포인트는 시계 방향으로 돌기 때문에 각 층마다 차례대로 값을 저장하기 어렵다는 것인데, 이를 해결하기 위해서 각 위치를 좌표화 하였다.

➡️ 2차원 배열을 생성하여 위치 별로 값을 저장할 수 있도록 하였다.

2️⃣ 규칙 찾기

➡️ 규칙을 확인해본 결과 아래 그림과 같았다.

➡️ 이동 방향이 시계 방향이므로 ① 아래 (down) / ② 오른쪽 (right) / ③ 위 (up) 순서를 반복하면서, 동시에 이동 횟수는 초기에 주어지는 n 값에서 하나씩 감소하는 형태를 보였다. 따라서 해당 규칙을 바탕으로 코드를 구성하였다.

➡️ 또한 좌표이동 규칙은 아래와 같았다.

① 아래 (down) ➡️ x 좌표 만 1씩 증가
② 오른쪽 (right) ➡️  y 좌표 만 1씩 증가
③ 위 (up) ➡️ x, y 좌표 모두 1씩 감소

3️⃣ 코드

class Solution {
    public static int[][] tri;
    // 들어갈 숫자
    public static int tmp = 1;
    public static int x = -1;
    public static int y = 0;
    
    public int[] solution(int n) {
        // 층 마다 숫자를 담을 배열
        tri = new int[n][n];
        
        // 이동 방향 확인 (down 부터 시작)
        boolean down = true;
        boolean right = false;
        boolean up = false;
        
        // 시계 방향으로 이동하면서 배열 채움
        for (int i=n; i>0; i--) {
            if (down) {
                down(i);
                // down ➡️ right
                down = false;
                right = true;
            }
            else if (right) {
                right(i);
                // down ➡️ up;
                right = false;
                up = true;
            }
            else if (up) {
                up(i);
                // up ➡️ down
                down = true;
                up = false;
            }
        }
        
        // 층 순서대로 answer 에 추가
        int[] answer = new int[tmp-1];
        int idx = 0;
                
        for (int m=0; m<n; m++) {
            for (int u=0; u<m+1; u++) {
                answer[idx++] = tri[m][u];
            }
        }
        
        return answer;
    }
    public static void down (int step) {
        for (int i=0; i<step; i++) {
            x++;      
            tri[x][y] = tmp;
            tmp ++;
        }
        return;
    }
    public static void right (int step) {
        for (int i=0; i<step; i++) {
            y++;
            tri[x][y] = tmp;
            tmp++;
        }
        return;
    }
    public static void up (int step) {
        for (int i=0; i<step; i++) {
            x--;
            y--;
            tri[x][y] = tmp;
            tmp++;
        }
        return;
    }
}

4️⃣ 결과

➡️ 테스트 케이스는 모두 통과하였으나, 현재는 조금 비효율적인 코드라고 생각해서 효율성 테스트가 있었다면 시간초과가 뜰 수도 있었을 것 같다.

💻 풀이 코드

[level 2] Title: 삼각 달팽이, Time: 19.16 ms, Memory: 132 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@b08764a