[JAVA] 프로그래머스 : 정수를 나선형으로 배치하기

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

우선, n이 4일때를 기준으로 문제를 이해해 보자.

첫 번째 for문을 보면 같은 행에서 시작을 한다. 즉, 0번째 줄에서 시작하는 것이다. 0번째 줄에서 시작해서 열(세로줄)을 하나씩 채우는 것이다. 그러면 배열의 첫 번째 줄에 1,2,3,4가 들어간다. 그 다음, rowStart를 1 증가시켜 시작 행을 1 증가시켜준다.

그 다음, 두 번째 for문을 보면 맨 마지막 열에서 그 아래로 내려가는 로직이다. 그럼 맨 마지막 줄의 세로줄이 4,5,6,7이 채워진다. 그 다음 맨 마지막 열을 채웠으므로 colEnd를 1 줄여주어 끝 열을 하나 단축시켜준다.

그 다음에는 for문을 이용하여 1씩 감소시켜 반복시켜 주면 된다.

정답 코드 1

class Solution {
    public int[][] solution(int n) {
        int[][] answer = new int[n][n];
        int num = 1; //배치할 숫자
        int rowStart = 0; //행(가로)
        int rowEnd = n-1;
        int colStart = 0; //열(세로)
        int colEnd = n-1;
        //처음에는 오른쪽 끝까지 이동
        while(rowStart <= rowEnd && colStart <= colEnd){ //아직 채우지 않은 행과 열이 있는지 판단
            for(int i=colStart; i<=colEnd; i++){ //세로꺼를 하나하나 채워야 함
                answer[rowStart][i] = num++; //0번째 행
            }
            rowStart++; //행 증가
            
            for(int i=rowStart; i<=rowEnd; i++){
                answer[i][colEnd] = num++; //맨 마지막 가로줄 하나씩 채우기
            }
            colEnd --; //한 칸 왼쪽으로
            
            if(rowStart <= rowEnd){
                for(int i=colEnd; i>=colStart; i--){
                    answer[rowEnd][i] = num++; //세로 채우기
                }
                rowEnd --; //한 칸 오른쪽으로
            }
            
            if(colStart <= colEnd){
                for(int i=rowEnd; i>=rowStart; i--){
                    answer[i][colStart] = num++; //가로 채우기
                }
                colStart ++;
            }
        }
        return answer;
    }
}

정답 코드 2

이 코드는 dx, dy를 사용하는 코드이다. 이 코드를 이해하는데 더 어려웠지만, 코드를 이해하고 나니 더 쉬웠다.

way는 방향을 나타내는 변수이다. 즉, dx와 dy를 합쳐 보면 {오른쪽, 아래, 왼쪽, 위}의 순서로 탐색을 진행한다. dx는 x좌표를, dy는 y좌표에 관여한다고 생각하면 이해하기가 쉽다.

좌표를 보면 헷갈리기 때문에 코드로 살펴봐야 한다.
0,0부터 시작이기 때문에 answer[0][0] = 1, visited[0][0] = true가 된다. 이 때 if문의 조건에 부합하지 않기 때문에 if문을 건너뛴다. 그러면 그 다음 while문의 반복에서 마지막 조건인 visited[0][0]==true에서 걸리기 때문에 way를 1 증가시켜준다. 그러면 x=0, y=1이 되고, answer[0][1] = 2, visited[0][1] = true가 되는 것이다.

즉, (0,0) -> (0,1)의 순서로 좌표가 채워지는 것이다.

만약, 나선의 방향을 변경하고 싶다면 dx,dy의 순서를 변경하면 된다.

import java.util.*;

class Solution {
    public int[][] solution(int n) {
    	int[] dx = {1,0,-1,0};
        int[] dy = {0,1,0,-1};
        
        boolean[][] visited = new boolean[n][n];
        int x = 0;
        int y = 0;
        int num = 1;
        int way = 0;
        int[][] answer = new int[n][n];
        while(num <= Math.pow(n,2)){
            answer[x][y] = num;
            visited[x][y] = true;
            if(x + dx[way] < 0 || x + dx[way] >= n || y + dy[way] < 0 || y + dy[way] >= n || visited[x+dx[way]][y+dy[way]]==true){
                way++;
                way %= 4;
            }
            //위의 조건을 모두 통과하는 경우에만 이동
            x = x + dx[way];
            y = y + dy[way];
            num++;
        }
        return answer;
    }
}