[Java] 프로그래머스 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 행렬 테두리 회전하기 with 자바

: ) YOUNG·2022년 5월 9일
2

알고리즘

목록 보기
125/411
post-thumbnail

문제

https://programmers.co.kr/learn/courses/30/lessons/77485


rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.



생각하기

어려운 문제는 아니었지만, 공간감각이 부족한 나한테는 복잡한 문제였던 것 같다.
머리로 암산해서 풀기는 무리였고, 손으로 직접써서 풀어가니 쉽게 풀 수 있었다.

동작

    	int count = 1;
    	for(int i=0; i<rows; i++) {
    		for(int j=0; j<columns; j++) {
    			map[i][j] = count;
    			count ++;
    		}
    	}

우선 전역변수map에 1부터 값이 증가하며 담기는 배열을 생성해주었다.


    	for(int i=0; i<len; i++) {
    		int x1 = queries[i][0];
    		int y1 = queries[i][1];
    		int x2 = queries[i][2];
    		int y2 = queries[i][3];

    		rotation(x1-1, y1-1, x2-1, y2-1);
    		list.add(min);
    	}

그리고 query로 들어오는 배열값을 매개변수로 rotation 메소드를 실행시킨다.


    static void rotation(int x1, int y1, int x2, int y2) {
    	min = Integer.MAX_VALUE / 16;
    	copy();

    	// 2 2 5 4 -> 1 1 4 3
    	// (1,1) -> (4,3) 회전
    	// 8부터 28까지를 회전 (중앙 빼고 테두리만)

    	// 상단 회전 
    	// temp1,1 -> map1,2  
    	// temp1,2 -> map1,3
    	for(int i=y1; i<y2; i++) {
    		min = Math.min(temp[x1][i], min);
    		map[x1][i+1] = temp[x1][i];
    	}

    	// 우측 회전
    	// temp 1,3 -> map 2,3
    	// temp 2,3 -> map 3,3
    	// temp 3,3 -> map 4,3
    	for(int i=x1; i<x2; i++) {
    		min = Math.min(temp[i][y2], min);
    		map[i+1][y2] = temp[i][y2];
    	}

    	// 하단 회전
    	// temp 4,3 -> map 4,2
    	// temp 4,2 -> map 4,1
    	for(int i=y2; i>y1; i--) {
    		min = Math.min(temp[x2][i], min);
    		map[x2][i-1] = temp[x2][i];
    	}

    	// 좌측 회전
    	// temp 2,1 -> map 1,1
    	// temp 3,1 -> map 2,1
    	// temp 4,1 -> map 3,1
    	for(int i=x2; i>x1; i--) {
    		min = Math.min(temp[i][y1], min);
    		map[i-1][y1] = temp[i][y1];
    	}

    } // End of rotaion

rotation함수를 통해서 배열 map을 회전시킨다.

여기서 회전시키기 전에 기존의 값을 가지고 있는 배열이 필요하므로 copy 메소드를 실행해서 map과 똑같은 크기와 값을 가지는 temp배열을 만들어준다.

temp의 값을 회전하는 좌표에 map을 넣어주면 map을 회전시킬 수 있다.

그리고 회전하는 동안 min에 최소값을 찾으며 갱신할 수 있도록 Math.min메소드를 넣어주면 답을 찾을 수 있게된다.




코드


import java.util.*;

class Solution {
    static int map[][];
	static int temp[][];
	static int rows, columns;
	static int min;

	// 문제 : x1행 y1열 x2행 y2열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전
	// 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return

    public int[] solution(int rows, int columns, int[][] queries) {
    	this.rows = rows;
    	this.columns = columns;
    	map = new int[rows][columns];
    	temp = new int[rows][columns];
    	int len = queries.length;
    	List<Integer> list = new ArrayList<>();

    	int count = 1;
    	for(int i=0; i<rows; i++) {
    		for(int j=0; j<columns; j++) {
    			map[i][j] = count;
    			count ++;
    		}
    	}

    	for(int i=0; i<len; i++) {
    		int x1 = queries[i][0];
    		int y1 = queries[i][1];
    		int x2 = queries[i][2];
    		int y2 = queries[i][3];

    		rotation(x1-1, y1-1, x2-1, y2-1);
    		list.add(min);
    	}

    	int size = list.size();
        int[] answer = new int[size];
        for(int i=0; i<size; i++) {
        	answer[i] = list.get(i);
        }

        return answer;
    } // End of solution

    // map배열 temp로 카피하는 메소드
    static void copy() {
    	for(int i=0; i<rows; i++) {
    		for(int j=0; j<columns; j++) {
    			temp[i][j] = map[i][j];
    		}
    	}
    } // End of copy

    static void rotation(int x1, int y1, int x2, int y2) {
    	min = Integer.MAX_VALUE / 16;
    	copy();

    	// 2 2 5 4 -> 1 1 4 3
    	// (1,1) -> (4,3) 회전
    	// 8부터 28까지를 회전 (중앙 빼고 테두리만)

    	// 상단 회전 
    	// temp1,1 -> map1,2  
    	// temp1,2 -> map1,3
    	for(int i=y1; i<y2; i++) {
    		min = Math.min(temp[x1][i], min);
    		map[x1][i+1] = temp[x1][i];
    	}

    	// 우측 회전
    	// temp 1,3 -> map 2,3
    	// temp 2,3 -> map 3,3
    	// temp 3,3 -> map 4,3
    	for(int i=x1; i<x2; i++) {
    		min = Math.min(temp[i][y2], min);
    		map[i+1][y2] = temp[i][y2];
    	}

    	// 하단 회전
    	// temp 4,3 -> map 4,2
    	// temp 4,2 -> map 4,1
    	for(int i=y2; i>y1; i--) {
    		min = Math.min(temp[x2][i], min);
    		map[x2][i-1] = temp[x2][i];
    	}

    	// 좌측 회전
    	// temp 2,1 -> map 1,1
    	// temp 3,1 -> map 2,1
    	// temp 4,1 -> map 3,1
    	for(int i=x2; i>x1; i--) {
    		min = Math.min(temp[i][y1], min);
    		map[i-1][y1] = temp[i][y1];
    	}

    } // End of rotaion
} // End of Solution class

0개의 댓글