[프로그래머스(Python/Java)] 행렬 테두리 회전하기

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

코딩테스트 연습 - 행렬 테두리 회전하기

 

배열의 원소 이동을 잘 구현할 수 있는지를 묻는 문제입니다.

 

아래 문제의 조건처럼 1 <= x1 < x2 <= rows, 1 <= y1 < y2 <= columns 라는 내용이 있고, 항상 시계 방향으로 회전한다고 했으므로 구현해야 하는 내용은 간단해지는데요.

 

문제 조건

다만, 범위 테두리에 있는 원소들을 시계 방향으로 어떻게 회전할 것인가를 잘 생각해야 합니다. 저보다 좋은 방법이 있을 수 있겠지만, 저는 시계 방향으로 해당 범위의 원소들을 큐에 쭉 담은 뒤 큐의 맨 뒤의 원소를 맨 앞에 배치하고 다시 원래 자리에 원소들을 재배치했습니다.

예시

예를 들어, 위와 같은 범위에 있는 테두리를 회전한다고 해볼까요? 그러면 우선 시작점(x1, y1)부터 끝점까지 담아줍니다.

Queue = [8, 9, 10, 16, 22, 28, 27, 26, 20, 14] 

그리고 해당 큐의 맨 마지막 원소를 빼서 맨 앞에 넣어줍니다.

Queue = [14, 8, 9, 10, 16, 22, 28, 27, 26, 20, 14] 

이제 큐에 존재하는 원소들을 다시 똑같이 시계 방향으로 회전하면서 원래 행렬에 배치해주면 됩니다.

 

시계 방향으로 원소를 탐색하는 로직은 아래 코드를 보면 쉽게 이해하실 수 있을 것 같습니다.

 

[풀이 - 파이썬]

from collections import deque
def show(graph):
    for i in range(len(graph)):
        print(*graph[i])

def rotate(matrix, x1, y1, x2, y2):
    min_value = 1000000
    movingQueue = deque() # 테두리의 값들을 담을 큐
    dx, dy = [0,1,0,-1], [1,0,-1,0] # 시계 방향
    x, y = x1, y1 # x, y위치를 나타내는 커서
    direction = 0 # 최초 방향은 동쪽
    # 시계 방향으로 회전하면서 테두리의 값을 큐에 담는다.
    while True:
        if min_value > matrix[x][y]: min_value = matrix[x][y]
        movingQueue.append(matrix[x][y])
        if y == y2 and x == x1:
            direction += 1
        if x == x2 and y == y2: 
            direction += 1
        if x == x2 and y == y1:
            direction += 1
        if x == x1+1 and y == y1:
            break
        x, y = x + dx[direction], y + dy[direction]

    # 테두리 회전
    first = movingQueue.pop()
    movingQueue.appendleft(first)
    
    x, y = x1, y1 # x, y위치를 나타내는 커서
    direction = 0 # 최초 방향은 동쪽
    # 시계 방향으로 회전하면서 다시 Matrix에 값을 채워 넣는다.
    while True:
        matrix[x][y] = movingQueue.popleft()
        if y == y2 and x == x1:
            direction += 1
        if x == x2 and y == y2: 
            direction += 1
        if x == x2 and y == y1:
            direction += 1
        if x == x1+1 and y == y1:
            break
        x, y = x + dx[direction], y + dy[direction]
    return min_value

def solution(rows, columns, queries):
    result = []
    # 처음 행렬의 모양 초기화, 테두리는 0
    matrix = [[0] * (columns+2) for _ in range(rows+2)]
    for i in range(1, rows+1):
        for j in range(1, columns+1):
            matrix[i][j] = (i-1) * columns + j

    for x1,y1,x2,y2 in queries:
        output = rotate(matrix, x1,y1,x2,y2)
        result.append(output)
    return result

[풀이 - 자바]

package PS;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Programmers_RotateMatrixBoundary {
    static int matrix[][];
    static int[] dx = {0,1,0,-1}; // 시계 방향
    static int[] dy = {1,0,-1,0};
    static int rotate(int x1, int y1, int x2, int y2){
        int min_value = 1000000;
        LinkedList<Integer> movingQueue = new LinkedList<>();
        int x = x1; // x, y위치를 나타내는 커서
        int y = y1;
        int direction = 0; // 최초 방향은 동쪽

        // 시계 방향으로 회전하면서 테두리의 값을 큐에 담는다.
        while(true){
            min_value = min_value > matrix[x][y] ? matrix[x][y] : min_value;
            movingQueue.add(matrix[x][y]);
            if(y == y2 && x == x1) direction++;
            if(x == x2 && y == y2) direction++;
            if(x == x2 && y == y1) direction++;
            if(x == x1+1 && y == y1) break;
            x += dx[direction];
            y += dy[direction];
        }
        // 테두리 회전
        int first = movingQueue.pollLast();
        movingQueue.addFirst(first);

        // 커서와 탐색 방향을 초기화하고 다시 Matrix에 값을 채워 넣는다.
        x = x1; y = y1; direction = 0;
        while(true){
            matrix[x][y] = movingQueue.pollFirst();
            if(y == y2 && x == x1) direction++;
            if(x == x2 && y == y2) direction++;
            if(x == x2 && y == y1) direction++;
            if(x == x1+1 && y == y1) break;
            x += dx[direction];
            y += dy[direction];
        }
        return min_value;
    }
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer;
        List<Integer> result = new ArrayList<>();
        // 처음 행렬의 모양 초기화, 테두리는 0
        matrix = new int[rows+2][columns+2];
        for(int i = 1; i < rows+1; i++){
            for(int j = 1; j < columns+1; j++){
                matrix[i][j] = (i-1) * columns + j;
            }
        }
        for(int i = 0; i < queries.length; i++){
            int x1 = queries[i][0]; int y1 = queries[i][1];
            int x2 = queries[i][2]; int y2 = queries[i][3];
            result.add(rotate(x1, y1, x2, y2));
        }
        answer = new int[result.size()];
        for(int i = 0; i < result.size(); i++){
            answer[i] = result.get(i);
        }
        return answer;
    }
}