かいてんマトリクスきょうかい

27115 ワード
コーディングテスト テキストリンク

しょかい


マトリクスを初期化する方法に従ってマトリクス()queryを埋め込み、回転マトリクスの方法回転()を宣言します.
このときrotate()では、回転ごとに移動するすべての数値にアクセスできるので、最高値を返します.
rotate()では、1つの数字を移動するたびに、現在位置の数字を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;
    }
}

改善された回答


テストの時間は思ったより長いです.
数字を1つずつ移動していくことを考えていると、終わりの場所から考えると並ばなくてもいいと思います.
開始点[x 1][y 1]の数字を一時的に記憶し、左枠から1つずつ移動する.(時計回りに回転)
移動後、[x 1][y 1+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

時間がずいぶん短縮された.
API開発
第六章オブジェクト向けプログラム設計