[프로그래머스/Lv. 2] 삼각 달팽이 (JAVA)

🔺 문제

프로그래머스

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {1, 0, -1}; // 남 -> 동 -> 북서 (행렬 기준)
    static int[] dy = {0, 1, -1};
    
    static int n;
    static int[][] map;
    
    public int[] solution(int n) {
        this.n = n;
        map = new int[n + 1][n + 1];
        map[0][0] = 1;
        
        int num = 1;
        int x = 0;
        int y = 0;
        int dir = 0;
        
        for(int i = 2 ; i <= n * n ; i++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            // 방문한 적 없고, 범위를 벗어나지 않을 때만 이동 가능
            if(map[nx][ny] == 0 && inRange(nx, ny)) {
                x = nx;
                y = ny;
                map[x][y] = ++num;
            }
            else {
                dir = (dir + 1) % 3;
            }
        }  
        
        
        List<Integer> list = new ArrayList<>();
        for(int[] i : map) {
            for(int j : i) {
                if(j != 0) {
                    list.add(j);
                }
            }
        }
        
        int[] answer = new int[list.size()];
        for(int i = 0 ; i < answer.length ; i++) {
            answer[i] = list.get(i);
        }
 
        return answer;
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < n);
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 달팽이의 이동방향을 봤을 때, 1 : 아래로 내려가고 (남) / 2 : 오른쪽으로 이동하고 (동) / 3 : 왼쪽 위(북서)으로 이동한다.

- 2차원 배열을 설정한 후, 달팽이를 2부터 n * n번까지 이동시킨다.

- 이 때, 방문한 적 없고, 범위를 벗어나지 않아야만 이동 가능하다.

- 그렇지 않다면, 방향을 전환해야 한다.

 

- 2차원 배열을 리스트로 받고, 리스트를 1차원 배열로 변환해 출력한다.

 

 

---

🔺 다른 풀이들

2차원 배열을 1차원 배열로 출력할 때 이렇게 해도 된다.

 

[프로그래머스 - Java] 삼각 달팽이(월간 코드 챌린지 시즌1)

int[] answer = new int[n * (n + 1) / 2];
 
int size = 0;
 
for(int i = 0 ; i < n ; i++){
    for(int j = 0 ; j < n ; j++){
        if(li[i][j] == 0) break;
        answer[size++] = li[i][j];
    }
}
 
return answer;

 

 

---

💬 느낀 점

코드트리에서 풀어본 문제라 그래도 혼자 힘으로 풀 수 있었다ㅠ

중간에 코드 한 줄 빠뜨려서 에러 나고 고친다고 멍한 시간도 좀 있었지만..

 

1회독	2회독	3회독	4회독	5회독
V	240626

 

 

(+2회독 240626)

import java.util.*;
 
class Solution {
    static int[] dx = {1,0,-1}; // 아래 오른쪽 대각선 위
    static int[] dy = {0,1,-1};
    
    static int n;
    static int[][] arr;
    
    public int[] solution(int n) {
        this.n = n;
                
        arr = new int[n][n];
        
        int num = 1;
        int x = 0;
        int y = 0;
        int dir = 0;
        arr[x][y] = num;
        
        int len = (n*(n+1))/2;  // 삼각 달팽이 칸 갯수
        while(num < len) {  // 배열의 모든 요소를 다 채우기 전까지 실행
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            // 격자 범위 내에 있고, 숫자가 들어간 적 없다면 값 채우기
            if(inRange(nx, ny) && arr[nx][ny] == 0) {
                arr[nx][ny] = ++num;
                x = nx;
                y = ny;
            }
            else {
                dir = (dir + 1) % 3;
            }
        }
        
        int[] answer = new int[len];
        int idx = 0;
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(arr[i][j] != 0) {
                    answer[idx++] = arr[i][j];
                }
            }
        }
        
        return answer;
    }
    
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }
}