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

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라. 

    

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

[내 코드]

import java.util.*; 

class Solution {
    
   
    public static ArrayList<Integer> arr;
    public static int sx;
    public static int sy;
    public static int ex;
    public static int ey; 
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {1, 0, -1, 0};
    public static int[][] map;
    
    public void DFS(int x, int y, int direction){
        
        if(x == sx && y == sy && arr.size()!= 0){
            return; 
        }
        
        int nx = x + dx[direction];
        int ny = y + dy[direction];
        
        if(sx<=nx && nx<=ex && sy<= ny && ny<= ey){
            arr.add(map[nx][ny]);
            DFS(nx, ny, direction);
        }else{
            direction += 1;
            nx = x + dx[direction];
            ny = y + dy[direction];
            arr.add(map[nx][ny]);
            DFS(nx, ny, direction); 
        }
        
        
        
        
    }
    
    public void DFS2(int x, int y, int direction){
        
        if(x == sx && y == sy && arr.size() == 0){
            return; 
        }
        
        int nx = x + dx[direction];
        int ny = y + dy[direction];
        
        if(sx<=nx && nx<=ex && sy<= ny && ny<= ey){
            map[nx][ny] = arr.get(0);
            arr.remove(0);
            DFS2(nx, ny, direction);
        }else{
            direction += 1;
            nx = x + dx[direction];
            ny = y + dy[direction];
            map[nx][ny] = arr.get(0);
            arr.remove(0);
            DFS2(nx, ny, direction); 
        }
        
        
        
        
    }
    
    public void print(){
        
        for(int i=1; i<=6; i++){
            for(int j=1; j<=6; j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        
        
    }
    
    
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        
        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++; 
            }
        }
        
        
        for(int i=0; i<queries.length; i++){
            sx = queries[i][0];
            sy = queries[i][1];
            ex = queries[i][2];
            ey = queries[i][3]; 
            arr = new ArrayList<>();
            
            DFS(sx, sy, 0);
            
            arr.add(0, arr.get(arr.size()-1));
            arr.remove(arr.size()-1);
            
            int minVal = Integer.MAX_VALUE;
            for(int j=0; j<arr.size(); j++){
                minVal = Math.min(minVal, arr.get(j));
            }
            answer[i] = minVal;
            
            DFS2(sx, sy, 0);
            
            
        }
        
        
        
        return answer;
    }
}

[참고 코드]

class Solution {
    
    public static int[][] matrix;
    
    
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        
        matrix = new int[rows+1][columns+1];
        
        int num = 1;
        
        for(int i=1; i<=rows; i++){
            for(int j=1; j<=columns; j++){
                matrix[i][j] = num++;
            }
        }
        
        for(int i=0; i<queries.length; i++){
            answer[i] = rotate(queries[i]);
        }
        
        return answer;
    }
    
    
    public int rotate(int[] query){
        
        int r1 = query[0];
        int c1 = query[1];
        int r2 = query[2];
        int c2 = query[3];
        
        int min = matrix[r1][c1];
        int temp = matrix[r1][c1];
        
        for(int i=r1; i<r2; i++){
            matrix[i][c1] = matrix[i+1][c1];
            min = Math.min(min, matrix[i][c1]);
        }
        
        for(int i=c1; i<c2; i++){
            matrix[r2][i] = matrix[r2][i+1];
            min = Math.min(min, matrix[r2][i]);
        }
        
        for(int i=r2; i>=r1+1; i--){
            matrix[i][c2] = matrix[i-1][c2];
            min = Math.min(min, matrix[i][c2]);
        }
        
        for(int i=c2; i>=c1+2; i--){
            matrix[r1][i] = matrix[r1][i-1];
            min = Math.min(min, matrix[r1][i]);
        }
        
        matrix[r1][c1+1] = temp;

        return min;
    }
    
    
}

 

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?

-> DFS를 2개 썼다

-> 이렇게 쓰는 작성하는 것이 최선일까?

-> 더 나은 방법이 있지 않을까?

-> 

- 문제가 무엇인가?

-> 이것을 어떻게 적용할 것인가?

-> 즉, 이렇게 푸는 것이 더 효율적이다

-> 이것을 어떻게 적용할 것인가?

-> 이것이 훨씬 나은 코드이다

-> 왜냐하면 DFS를 쓰지도 않고, 그냥 구현을 한 번만 사용했기 때문이다. 

-> 내가 직접 풀어본다면 어떻게 풀겠는가?

-> 문제가 무엇인가?

-> 어떻게 대입을 할 것인가?

-> 대입을 한다는 것이 무엇인가?

-> 회전 방향을 바꾸는 방법이 있다

-> 회전 방향을 바꾼다는 것이 무엇 인가?

-> 시간적으로 훨씬 효율적이다

-> 또한 구현 로직도 더 간단하다

-> 단, 방향을 반대로 하는 아이디어를 떠올릴 수 있어야 한다