[prog 77485] 행렬 테두리 회전하기

프로그래머스

 

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        
        int[][] referenceMap = new int[rows + 1][columns + 1]; // 값 참조용 배열
        int[][] map = new int[rows + 1][columns + 1];          // 회전시킨 값 저장할 배열
        
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= columns; c++) {
                referenceMap[r][c] = ((r - 1) * columns + c);
                map[r][c] = ((r - 1) * columns + c);
            }
        }
        
        // ----- 입력 끝 -----
        
        // 회전
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            int x1 = query[0], y1 = query[1];
            int x2 = query[2], y2 = query[3];
            int min = Integer.MAX_VALUE;
            
            // 위쪽 변
            for (int j = y1 + 1; j <= y2; j++) {
                map[x1][j] = referenceMap[x1][j - 1];
                min = Math.min(min, map[x1][j]);
            }
            // 오른쪽 변
            for (int j = x1 + 1; j <= x2; j++) {
                map[j][y2] = referenceMap[j - 1][y2];
                min = Math.min(min, map[j][y2]);
            }
            // 아래쪽 변
            for (int j = y2 - 1; j >= y1; j--) {
                map[x2][j] = referenceMap[x2][j + 1];
                min = Math.min(min, map[x2][j]);
            }
            // 왼쪽 변
            for (int j = x2 - 1; j >= x1; j--) {
                map[j][y1] = referenceMap[j + 1][y1];
                min = Math.min(min, map[j][y1]);
            }
            
            answer[i] = min;
            
            // 다음 회전을 위해, referenceMap에 map을 복사
            for (int r = 1; r <= rows; r++) {
                for (int c = 1; c <= columns; c++) {
                    referenceMap[r][c] = map[r][c];
                }
            }
        }
        
        return answer;
    }
}

 

1. 문제 요약

이 문제는 주어진 rows x columns 크기의 행렬에서 주어진 영역의 테두리를 시계방향으로 회전시키는 작업을 여러 번 수행한 후, 각 회전에서 이동한 숫자들 중 가장 작은 숫자를 구하는 문제입니다. 주어진 회전 명령을 차례로 수행하며 각 회전의 최소값을 기록하여 반환해야 합니다.

 

2. 핵심 아이디어

1. 행렬 초기화:
   • rows x columns 크기의 행렬을 초기화합니다. 각 위치 (i, j)에 대해 (i-1) * columns + j의 값을 가지도록 설정합니다.
2. 회전 로직 구현:
   • 각 회전 명령에 대해 테두리의 숫자들을 시계방향으로 한 칸씩 이동시키는 로직을 구현합니다. 이동 시 가장 작은 숫자를 기록합니다.
   • 회전은 네 부분으로 나눠서 진행합니다:
     1. 위쪽 변: 오른쪽으로 이동
     2. 오른쪽 변: 아래로 이동
     3. 아래쪽 변: 왼쪽으로 이동
     4. 왼쪽 변: 위로 이동
3. 이동 후 값 갱신:
   • 각 회전이 끝난 후에는 결과를 저장할 map 배열에 값을 갱신하고, 다음 회전을 위해 referenceMap에 복사합니다.
4. 최소값 저장:
   • 각 회전마다 최소값을 계산하여 answer 배열에 저장합니다.

 

3. 출제 의도

1. 배열 및 행렬 조작 능력:
   • 2차원 배열(행렬)을 초기화하고 조작하는 능력을 요구합니다. 특히 특정 부분(테두리)을 선택하여 조작하는 능력을 테스트합니다.
2. 구현력:
   • 문제의 요구 사항을 정확히 이해하고, 이를 코드로 구현하는 능력을 측정합니다. 여기에는 입력과 출력을 처리하는 능력, 주어진 조건에 맞게 로직을 작성하는 능력이 포함됩니다.
3. 시뮬레이션 및 시계 방향 회전 로직 구현:
   • 주어진 명령에 따라 행렬의 특정 부분을 시계방향으로 회전시키는 시뮬레이션 능력을 테스트합니다. 이는 각 명령에 따라 정확한 위치의 값을 업데이트하고, 최소값을 추적하는 능력을 포함합니다.
4. 최적화 및 효율성:
   • 효율적으로 문제를 해결하기 위해 불필요한 작업(예: 중복된 배열 복사)을 피하고, 최소한의 연산으로 문제를 해결하는 능력을 측정합니다. 특히, 다수의 회전 명령이 주어졌을 때 효율적으로 처리할 수 있는지 테스트합니다.
5. 기본적인 수학적 사고 및 문제 해결 능력:
   • 문제를 해결하기 위해 기본적인 수학적 사고와 논리적 사고가 필요합니다. 예를 들어, 인덱스를 계산하고 업데이트하는 과정에서 정확한 수학적 사고가 요구됩니다.
6. 경계 조건 및 예외 처리 능력:
   • 배열의 경계를 넘어가지 않도록 주의하고, 다양한 입력 조건에 대해 올바르게 처리하는 능력을 테스트합니다.

이 문제를 해결하는 과정에서, 프로그래머는 복잡한 로직을 이해하고 구현할 수 있는 능력을 보여줄 수 있습니다. 이를 통해 면접관이나 문제 출제자는 프로그래머의 전반적인 알고리즘 문제 해결 능력, 구현 능력, 그리고 최적화 능력을 평가할 수 있습니다.