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

https://school.programmers.co.kr/learn/courses/30/lessons/68645?language=java

프로그래머스

 

1번 풀이

class Solution {
    static int [] dx = {1,0,-1};
    static int [] dy = {0,1,-1};
    public int[] solution(int n) {
        
        int [][] temp = new int[n][n];
        
        int x = 0; 
        int y = 0;
        int val = 1;
        
        while (true) {
            // 아래로 이동
            while(true) {
                temp[y][x] = val++;
                if (y + 1 == n || temp[y+1][x] != 0) break;
                y += 1;
            }
            
            // 오른쪽으로 진행 x 
            if (x + 1 == n || temp[y][x+1] != 0) break;
            x += 1;
        
            // 오른쪽으로 이동
            while (true) {
                temp[y][x] = val++;
                if (x + 1 == n || temp[y][x+1] != 0) break;
                x += 1;
            }
            
            // 왼쪽 위로 이동x
            if (temp[y-1][x-1] != 0) break;
            x -= 1;
            y -= 1;
        
            // 반시계 방향으로 이동
            while(true) {
                temp[y][x] = val++;
                if (temp[y-1][x-1] != 0) break;
                x -= 1;
                y -= 1;
            }
            
            if (y + 1 == n || temp[y+1][x] != 0) break;
            y += 1;
        }
        
        int[] answer = new int[val - 1];
        int idx = 0;
        for(int i = 0; i < temp.length; i++){
            for(int j = 0; j <= i; j++) {
                answer[idx++] = temp[i][j];
            }
        }
        return answer;
    }
}

 

2번 풀이 (bfs 처럼 방향을 정의)

문제 풀이 접근

1. 진행하는 방향은 아래, 오른쪽, 왼쪽 대각선 위로 진행된다.

2. 진행을 하며 방문 처리를 해주고, 끝  부분에 도달했을 때 방향을 바꿔줘야 한다.

3. 최종적으로 더 방문할 지역이 없다면, break!

 

주의사항
1. 항상 방향은 아래부터 시작해야 한다.
bfs를 할 떄는 방향 순서가 상관없으니 아무 생각 없이 작성했는데, 이 문제에선 방향이 무조건 아래로부터 가야 한다.
2. temp[nx][ny]가 0이 아닐때를 체크해야 한다.
이미 숫자가 채워져 있다는 의미기 때문에, 그 때도 방향을 바꿔 줘야 한다.

3. 마지막에 nx, ny값을 x,y에 재할당 해주기!! 

class Solution {
    static int [] dx = {1,0,-1};
    static int [] dy = {0,1,-1};
    public int[] solution(int n) {
        
        
        int [][] temp = new int[n][n];
        int x = 0;
        int y = 0;
        int val = 1;
        int dir = 0;
        
        while (true) {
            temp[x][y] = val++;
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            
            if (nx == n || ny == n || nx < 0 || ny < 0 || temp[nx][ny] != 0) {
                dir = (dir + 1) % 3;
                nx = x + dx[dir];
                ny = y + dy[dir];
                if (nx == n || ny == n || nx < 0 || ny < 0 || temp[nx][ny] != 0) break;
            }
            
            x = nx;
            y = ny;
        }
        int[] answer = new int[val-1];
        int idx = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++) {
                answer[idx++] = temp[i][j];
            }
        }
        return answer;
    }
}

 

문제풀이 회고

어제 분명히 푼 문제인데 오늘 다시 풀어보려고 하니 버벅거렸다. 

 

아직 매커니즘을 완벽하게 이해하고 있지 않아서인것 같다. 

 

1. 진행하려는 방향에 따른 nx,ny값을 정의하여 방문 표시

2.  만약에 범위 초과 했거나 방문했다면, 방향을 바꿔주고 그 지점부터 다시 시작.

3. 모든 지점을 돌았는데 더 갈 곳이 없다면 break.

4. x = nx, y = ny처럼 항상 값을 재정의