행렬 테두리 회전하기 - 프로그래머스 (Java, Level 2)

​

처음 풀이

행렬 초기화하는 메소드 fillMatrix() query에 맞게 행렬을 회전하는 메소드 rotate()를 선언한다.

이 때, rotate()에서, 각 회전 당 이동하는 모든 숫자에 접근 가능하니 최솟값을 리턴한다.

rotate()에서 숫자 한 칸씩 이동시킬 때, Queue에 현재 위치의 숫자를 담은 후, Queue 맨 앞 숫자로 치환한다.

 

import java.util.*;

class Solution {
    int[][] board;
    Queue<Integer> queue;

    public int[] solution(int rows, int columns, int[][] queries) {

        board = new int[rows][columns];
        queue = new LinkedList<>();

        fillMatrix(rows, columns);

        //각 회전 당, 이동한 숫자들 중 최솟값 담을 배열
        int[] answer = new int[queries.length];

        for(int i=0; i<answer.length; i++) {
            answer[i] = rotate(queries[i]);
        }//for end
        
        return answer;

    }//solution() end

    //행렬 값 채우는 메소드
    public void fillMatrix(int rows, int columns) {
        int n = 0;
        for(int i=0; i<rows; i++) {
            for(int j=0; j<columns; j++) {
                board[i][j] = ++n;
            }
        }
    }

    //query 범위의 행렬 테두리 회전하고, 최솟값 리턴하는 메소드
    public int rotate(int[] query) {
        //queue 비우기
        queue.clear();

        int x1 = query[0]-1;
        int y1 = query[1]-1;
        int x2 = query[2]-1;
        int y2 = query[3]-1;

        int min = board[x1][y1];

        queue.add(board[x1][y1]);

        //위 테두리
        for(int i=1; i<=y2-y1; i++) {
            min = Math.min(min, board[x1][y1+i]);
            queue.add(board[x1][y1+i]);
            board[x1][y1+i] = queue.poll();
        }//for end

        //오른쪽 테두리
        for(int i=1; i<=x2-x1; i++) {
            min = Math.min(min, board[x1+i][y2]);
            queue.add(board[x1+i][y2]);
            board[x1+i][y2] = queue.poll();
        }//for end

        //아래 테두리
        for(int i=1; i<=y2-y1; i++) {
            min = Math.min(min, board[x2][y2-i]);
            queue.add(board[x2][y2-i]);
            board[x2][y2-i] = queue.poll();
        }//for end

        //왼쪽 테두리
        for(int i=1; i<=x2-x1; i++) {
            min = Math.min(min, board[x2-i][y1]);
            queue.add(board[x2-i][y1]);
            board[x2-i][y1] = queue.poll();
        }//for

        return min;
    }
}

 

 

개선된 풀이

 

생각했던 것보다 테스트의 시간이 오래 걸린다.

고민하다가 숫자를 한 칸씩 이동할 때, 끝나는 지점부터 고려하면 queue를 이용하지 않아도 되지 않을까 싶었다.

 

시작지점[x1][y1] 숫자 임시 저장하고, 왼쪽 테두리부터 한 칸씩 이동했다. (시계방향으로 회전하기 때문에)

다 이동한 후에는 [x1][y1+1] 위치에는 임시 저장한 값을 넣어준다.

 

public int rotate(int[] query) {
        int x1 = query[0]-1;
        int y1 = query[1]-1;
        int x2 = query[2]-1;
        int y2 = query[3]-1;
   
        //시작지점 값 임시저장
        int temp = board[x1][y1];
        
        int min = board[x1][y1];

        //왼쪽 테두리
        for(int i=x1; i<x2; i++) {
            min = Math.min(min, board[i][y1]);
            board[i][y1] = board[i+1][y1];
        }//for end

        //아래 테두리
        for(int i=y1; i<y2; i++) {
            min = Math.min(min, board[x2][i]);
            board[x2][i] = board[x2][i+1];
        }//for end

        //오른쪽 테두리
        for(int i=x2; i>x1; i--) {
            min = Math.min(min, board[i][y2]);
            board[i][y2] = board[i-1][y2];
        }//for end

        //아래 테두리
        for(int i=y2; i>y1; i--) {
            min = Math.min(min, board[x1][i]);
            board[x1][i] = board[x1][i-1];
        }//for end

        board[x1][y1+1] = temp;

        return min;
    }//rotate2() end

 

시간이 꽤나 단축되었다.