[77485] 행렬 테두리 회전하기

✔ 행렬 테두리 회전하기

[프로그래머스 77485]

문제 분석하기

회전하는 방향과 반대 방향으로 진행하며 데이터를 보존하면서 회전하도록 함

 

예) [2, 2, 5, 4]일 때 x1 = 1, y1 = 1, x2 =  4, y2 = 3

1) ↑ 방향

map[1][1] = map[2][1]이므로 8에서 14로 변경

map[2][1] = map[3][1]이므로 14에서 20으로 변경

map[3][1] = map[4][1]이므로 20에서 26로 변경

이때 사라지게 되는 값인 8을 별도로 저장

2) ← 방향

map[4][1] = map[4][2]이므로 26에서 27로 변경

map[4][2] = map[4][3]이므로 27에서 28로 변경

3) ↓ 방향

map[4][3] = map[3][3]이므로 28에서 22로 변경

map[3][3] = map[2][3]이므로 22에서 16으로 변경

map[2][3] = map[1][3]이므로16에서 10으로 변경

4) → 방향

map[1][3] = map[1][2]이므로 10에서 9로 변경

map[1][2] = map[1][1]이므로 9에서 8로 변경 (이때 위에서 별도로 저장해둔 8을 저장)

손으로 풀어보기

1. x1, y1, x2, y2 구하기
2. ↑ 방향, ← 방향, ↓ 방향, → 방향으로 회전하기
   • 이때 ↑ 방향의 첫 번째 값을 저장해둔 후 마지막에 사용
   • 회전하면서 가장 작은 값을 갱신하며 가장 작은 값을 배열에 저장
3. 이를 회전들의 목록만큼 반복

슈도코드 작성하기

rows, columns(행렬의 세로, 가로 길이)
queries(회전들의 목록)
answer(회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들)
map(행렬들을 저장한 배열)
map에 순서대로 숫자를 저장
for(i -> queries만큼) {
    x1, y1, x2, y2 구하기
    min(최소값)
    start(회전에 따라 사라지게 되는 첫 번째 값)
    ↑ 방향 회전하며 최솟값 찾기 (좌측 부분 회전) 
    ← 방향 회전하며 최솟값 찾기 (하단 부분 회전)
    ↓ 방향 회전하며 최솟값 찾기 (우측 부분 회전)
    → 방향 회전하며 최솟값 찾기 (상단 부분 회전)
    마지막 부분에 start 저장
    answer[i] = min 저장
}
answer 반환

코드 구현하기

/**
 * 77485) 행렬_테두리_회전하기
 */
public class L065_77485 {
    // rows, columns(행렬의 세로, 가로 길이)
    // queries(회전들의 목록)
    public int[] solution(int rows, int columns, int[][] queries) {
        // answer(회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들)
        int[] answer = new int[queries.length];
        // map(행렬들을 저장한 배열)
        int[][] map = new int[rows][columns];
        // map에 순서대로 숫자를 저장
        int index = 1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                map[i][j] = index++;
            }
        }
        for (int i = 0; i < queries.length; i++) {
            // x1, y1, x2, y2 구하기
            int x1 = queries[i][0] - 1;
            int y1 = queries[i][1] - 1;
            int x2 = queries[i][2] - 1;
            int y2 = queries[i][3] - 1;
            // min(최소값)
            int min = Integer.MAX_VALUE;
            // start(회전에 따라 사라지게 되는 첫 번째 값)
            int start = map[x1][y1];
            // ↑ 방향 회전하며 최솟값 찾기 (좌측 부분 회전)
            for (int j = x1; j < x2; j++) {
                min = Math.min(min, map[j][y1]);
                map[j][y1] = map[j + 1][y1];
            }
            // ← 방향 회전하며 최솟값 찾기 (하단 부분 회전)
            for (int j = y1; j < y2; j++) {
                min = Math.min(min, map[x2][j]);
                map[x2][j] = map[x2][j + 1];
            }
            // ↓ 방향 회전하며 최솟값 찾기 (우측 부분 회전)
            for (int j = x2; j > x1; j--) {
                min = Math.min(min, map[j][y2]);
                map[j][y2] = map[j - 1][y2];
            }
            // → 방향 회전하며 최솟값 찾기 (상단 부분 회전)
            for (int j = y2; j > y1; j--) {
                min = Math.min(min, map[x1][j]);
                map[x1][j] = map[x1][j - 1];
            }
            // 마지막 부분에 start 저장
            map[x1][y1 + 1] = start;
            // answer[i] = min 저장
            answer[i] = min;
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L065_77485 solution = new L065_77485();

        int rows = 6;
        int columns = 6;
        int[][] queries = {
                { 2, 2, 5, 4 },
                { 3, 3, 6, 6 },
                { 5, 1, 6, 3 }
        };

        int[] result = solution.solution(rows, columns, queries);

        System.out.println(Arrays.toString(result));
    }
}