[ 프로그래머스 - java & Kotlin ] 행렬 테두리 회전하기 ( 자바 & 코틀린 )

( 2021 Dev-Matching: 웹 백엔드 개발자(상반기) / 행렬 테두리 회전하기 )

 

[문제]

문제 설명

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

• x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

제한사항

• rows는 2 이상 100 이하인 자연수입니다.
• columns는 2 이상 100 이하인 자연수입니다.
• 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
  • 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
• queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
• queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
  • x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
  • 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

입출력 예시

rows	columns	queries	result
6	6	[[2,2,5,4],[3,3,6,6],[5,1,6,3]]	[8, 10, 25]
3	3	[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]	[1, 1, 5, 3]
100	97	[[1,1,100,97]]	[1]

입출력 예 #1

입출력 예 #2

입출력 예 #3

• 이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.

---

[풀이]

아래 그림처럼 (빨간색 숫자가 순서입니다.)

첫 번째 숫자를 임시 저장 -> 왼쪽 변부터 반시계 방향으로 한 칸씩 앞으로 -> 마지막 칸에 임시 저장한 tmp 저장

이러한 방법을 생각하시면 rotation함수를 구현하여 풀이를 할 수 있습니다.

(그림이 생각보다 별로네요...😅)

rotation 함수 동작방식

 

---

[주의]

간단히 구현만 하면 끝나는 문제라 주의할 점은 딱히 없으나 저의 경우는 rows, columns를 바꿔서 생각해서 많이 헤매었습니다ㅠㅜ

rows, columns를 바꾸어도 테스트에서 1번, 2번은 통과했기 때문에 의심을 안 했는데 행과 열을 바꿔서 선언을 했을 줄이야...

---

[코드]

자바

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        // 숫자를 담을 행렬
        int[][] arr = new int[rows][columns];
        // 행렬 초기화
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++) arr[i][j] = i * columns + j + 1;
        }
        // queries안에 정보를 rotation을 통해 회전
        for(int i = 0; i < queries.length; i++) 
            answer[i] = rotation(arr, queries[i][1] - 1, queries[i][0] - 1, queries[i][3] - 1, queries[i][2] - 1);
        
        return answer;
    }
    // 왼쪽 위, 오른쪽 아래 좌표를 받으면 시계방향으로 회전 후 가장 작은 값을 반환하는 함수
    public int rotation(int[][] arr, int x1, int y1, int x2, int y2){
        int min = arr[y1][x1];  // 시작값을 최소 값으로 초기화
        int tmp = arr[y1][x1];  // 처음 시작값을 마지막에 넣어주기 위해 임시 저장
        // 왼쪽 회전
        for(int i = y1; i < y2; i++){
            arr[i][x1] = arr[i + 1][x1];
            min = Math.min(min, arr[i][x1]);
        }
        // 아래쪽 회전
        for(int i = x1; i < x2; i++){
            arr[y2][i] = arr[y2][i + 1];
            min = Math.min(min, arr[y2][i]);
        }
        // 왼쪽 회전
        for(int i = y2; i > y1; i--){
            arr[i][x2] = arr[i - 1][x2];
            min = Math.min(min, arr[i][x2]);
        }
        // 위쪽 회전
        for(int i = x2; i > x1 + 1; i--){
            arr[y1][i] = arr[y1][i - 1];
            min = Math.min(min, arr[y1][i]);
        }
        // 마지막 값 이동
        arr[y1][x1 + 1] = tmp;
        
        return min;
    }
}

코틀린

class Solution {
    fun solution(rows: Int, columns: Int, queries: Array<IntArray>): IntArray {
        val map = Array<IntArray>(rows){ i -> IntArray(columns){ i * columns + it + 1 } }
        return IntArray(queries.size){ rotation(queries[it], map) }
    }
    
    fun rotation(info:IntArray, map:Array<IntArray>):Int{
        var x1 = info[1]-1
        var y1 = info[0]-1
        var x2 = info[3]-1
        var y2 = info[2]-1
        var min = map[y1][x1]
        var tmp = map[y1][x1]
        
        for(i in y1 until y2){
            map[i][x1] = map[i+1][x1]
            min = min.coerceAtMost(map[i][x1])
        }
        
        for(i in x1 until x2){
            map[y2][i] = map[y2][i+1]
            min = min.coerceAtMost(map[y2][i])
        }
        
        for(i in y2 downTo y1+1){
            map[i][x2] = map[i-1][x2]
            min = min.coerceAtMost(map[i][x2])
        }
        
        for(i in x2 downTo x1+1){
            map[y1][i] = map[y1][i-1]
            min = min.coerceAtMost(map[y1][i])
        }
        map[y1][x1+1] = tmp
        
        return min
    }
}

 

문제 링크

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

 

첫 글이었는데 유용하셨는지 모르겠습니다.

요즘 안드로이드가 코틀린으로 바뀌고 있어서 앞으로도 코틀린 풀이로 코딩 테스트를 올려볼까 합니다.

부족한 점이 있다면 많이 많이 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄