프로그래머스 (Dev-Matching 기출) | LV.2 행렬 테두리 회전하기 - 구현

⬛ 프로그래머스 (Dev-Matching 기출) | LV.2 행렬 테두리 회전하기 - 구현

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

프로그래머스

설명

설명2

---

💚문제 접근 방식

• 시계방향은 (우→하→좌→상) 순으로 돌아야 하고, 매번 prev로 직전값을 현재 map에 담으면서 움직인다.
• 매번 쿼리로 들어오는 (x1, y1, x2, y2) 의 테두리만 돌아야 한다.

(1) map[][] 2차원에 차례로 값을 세팅해준다.

(2) rotate() 함수에 query를 보내서, 해당 쿼리의 min 값을 반환받는다.

→ prev 변수에 맨 첫 시작 x1, y1 값을 담아두고,

→ 우측, 하강, 좌측, 상승 모두 for문 돌면서 매번 갱신되는 prev 값을 현재값에 세팅해주면 된다.

(3) 담긴 min값 반환하면됨

→ 직전값을 prev에 담아 현재값 세팅한 후 prev 갱신해주는 흐름이다.

풀이 그림

💚 제출 코드

import java.util.*;
class Solution {
    public int[][] map;
    public ArrayList<Integer> answer;
    //회전시키기 
    public int rotate(int[] query){
        int x1 = query[0];
        int y1=  query[1];
        int x2 = query[2];
        int y2 = query[3];
        
        int prev = map[x1][y1];
        int min = prev;
        
        //우측
        for(int i= y1+1; i<=y2; i++){
            int tmp = map[x1][i];
            map[x1][i] = prev;
            min = Math.min(min, prev);
            prev = tmp; //직전값은 기존의 값으로 세팅 
        }
        //하강
        for(int i=x1+1; i<=x2; i++){
            int tmp = map[i][y2];
            map[i][y2] = prev;
            min = Math.min(min, prev);
            prev = tmp; //기존값으로 세팅 
        }
        
        //좌측
        for(int i=y2-1; i>=y1; i--){
            int tmp = map[x2][i];
            map[x2][i] = prev;
            min = Math.min(min, prev);
            prev = tmp;
        }
        //상승
        for(int i=x2-1; i>=x1; i--){
            int tmp = map[i][y1];
            map[i][y1] = prev;
            min = Math.min(min, prev);
            prev = tmp;
        }
        
        return min;
    }
    //솔루션 함수 
    public List<Integer> solution(int rows, int columns, int[][] queries) {
        answer = new ArrayList<Integer>();
        // 맵 초기화
        map = new int[rows+1][columns+1];
        int num = 1;
        for(int i = 1; i <= rows; i++){
            for(int j = 1; j <= columns; j++){
                map[i][j] = num;
                num++;
            }  
            
        }
        for(int i = 0; i < queries.length; i++){
            answer.add(rotate(queries[i]));   
        }

        return answer;
    }

}

💚 시간복잡도

• 주어진 행렬 rowsXcolumns 는 각각100이고, queries 행의 개수가 10,000이다. map 2차원 배열 초기화 시, 최악으로 O(10,000) 가 나오고, 회전 쿼리가 10,000개 주어질 경우 대략 O(10^8) 정도 나온다. 10^9 가 통상 1초니까 괜찮다고 본다.

💚 회고

• 너무 복잡하게 생각하면 어려운 문젠데, 규칙적인 테두리의 좌표 증가, 감소 부분만 두고 prev를 매번 갱신해나가며 min값을 업데이트하면 되는 문제였다. 그래도 풀면서 꽤나 헷갈려서 애 먹었다.