[프로그래머스] 77485번 : 행렬 테두리 회전하기

2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 행렬 테두리 회전하기 문제를 풀어보았다.

이처럼 정해진 사각형 안의 테두리를 시계방향으로 회전하면서 매 반복마다 그때 업데이트 된 값들의 최소값을 반환하는 문제였다.

최대 크기 100x100, 최대 회전 개수 10_000 이기에
최대 약 400번의 연산을 10_000번 하기에 4_000_000 정도로 적당히 효율적인 구조만 사용한다면 시간초과는 나지 않는다.

디버깅이 없는 환경에서 코드를 짜다보니까 내가 변수값 하나만 잘못 작성해도 문제가 어딘지 찾기 힘들었다..
변수 하나 잘못 작성해서 뜬 RuntimeException으로 Index 오류가 나서 내 로직이 잘못된 줄 알고, 삽질을 좀 했다;;
역시 IDEA 는 굉장히 엄청난 개발 도구인걸 매번 느낀다.

---

해결 자체는 간단하다. 배열을 직접 돌리는 것이다.
여기서 각 모서리마다 가야할 방향은 1개로 각자 고정되어있기에 command를 통해 설정했다.

여기서 이전값의 정보를 들고, 다음값을 업데이트해야한다.
List, Queue, Stack 정도를 고민해봤었는데, 넣고 빼는 작업만 하고 리스트 정보 자체를 저장할 것이 아니기에 List는 탈락.
Queue가 사실 작업하는 FIFO에 맞게 어울리지만, 2개이상 데이터가 쌓일 일이 없기 때문에 Stack을 활용했다.

나머지는 주석을 참고하면 간단하게 해결된다.

import java.util.*;

/*
최대 크기 100x100
init : 1~n*m 까지의 초기값
최대 회전 개수 10_000

회전이 연속적으로 이루어지기에 실제 배열에서 옮기는 작업이 필요.
또한 어떻게 그 안에서 최소값을 찾을지 고민.
어떻게 효율적으로?
[2,2,5,4]
2,2 -> 2,3 -> 2,4 -> 3,4 -> 4,4 -> 5,4 -> 5,3 -> 5,2 -> 4,2 -> 3,2 -> 2,2
해당 값들을 stack에 넣고, 빼면서 업데이트 - 최소값을 비교
*/

class Solution {
    public class Point {
        int i;
        int j;
        int value;
        
        public Point(int i, int j, int value) {
            this.i = i;
            this.j = j;
            this.value = value;
        }
    }
    
    public int[] solution(int rows, int columns, int[][] queries) {
        List<Integer> result = new ArrayList<>();
        int[][] metrix = new int[rows+1][columns+1];
        int temp = 1;
        for (int i=1; i<=rows; i++) {
            for (int j=1; j<=columns; j++) {
                metrix[i][j] = temp++;
            }
        }
        
        for (int[] query : queries) {
            if (queries.length == 1) { // 회전 횟수가 1이라면 시작 값 반환
                result.add(metrix[query[0]][query[1]]);
                break;
            }
            
            int si = query[0];
            int sj = query[1];
            int ei = query[2];
            int ej = query[3];
            
            //초기 설정
            Stack<Point> stack = new Stack<>();
            stack.push(new Point(si, sj, metrix[si][sj]));
            int min = metrix[si][sj]; 
            String command = "RIGHT"; // RIGHT, DOWN, LEFT, UP, STOP
            
            while(!stack.isEmpty()) {
                Point p = stack.pop();
                if (command.equals("STOP")) break;
                
                int mi = p.i;
                int mj = p.j;
                int value = p.value;
                switch (command) {
                    case "RIGHT": 
                        mj++;
                        if (mj == ej) command = "DOWN";
                        break;
                    case "DOWN":
                        mi++;
                        if (mi == ei) command = "LEFT";
                        break;
                    case "LEFT":
                        mj--;
                        if (mj == sj) command = "UP";
                        break;
                    case "UP":
                        mi--;
                        if (mi == si) command = "STOP";
                        break;
                }
                min = Math.min(min, value); // 최소 값 업데이트
                stack.push(new Point(mi, mj, metrix[mi][mj])); // 다음 탐색 값 push
                metrix[mi][mj] = value; // 다음 값을 이전 값으로 업데이트
            }
            // this.print(rows, columns, metrix);
            result.add(min);
        }
        
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public void print(int rows, int columns, int[][] metrix) {
        for (int i=1; i<=rows; i++) {
            for (int j=1; j<=columns; j++) {
                System.out.print(metrix[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }
}