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

행렬 테두리 회전하기

문제 링크

행렬 테두리 회전하기

분석

2차원 배열이 주어지지 않으므로, 직접 $rows \times columns$ 크기의 2차원 벡터를 생성하고, 1부터 순서대로 값을 채워야 합니다.

쿼리의 요소를 하나씩 처리해야합니다.
주어진 범위의 테두리에서 시계방향으로 회전하면서 가장 작은 값을 찾아 기록해야합니다.
즉, 회전 순서는 오른쪽, 아래, 왼쪽, 위가 됩니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    
    // 2차원 배열 초기화
    vector<vector<int>> matrix(rows, vector<int>(columns));
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            matrix[i][j] = i * columns + (j + 1);
        }
    }
    
    // 쿼리를 처리하는 반복문
    for (auto query : queries)
    {
        int y1 = query[0] - 1, x1 = query[1] - 1;
        int y2 = query[2] - 1, x2 = query[3] - 1;
        
        // 회전을 위한 임시 저장
        int prevValue = matrix[y1][x1];
        // 최소값
        int minValue = prevValue;
        
        // 오른쪽으로
        for (int i = x1; i < x2; ++i)
        {
            swap(matrix[y1][i + 1], prevValue);
            minValue = min(minValue, prevValue);
        }
        
        // 아래로
        for (int i = y1; i < y2; ++i)
        {
            swap(matrix[i + 1][x2], prevValue);
            minValue = min(minValue, prevValue);
        }
        
        // 왼쪽으로
        for (int i = x2; i > x1; --i)
        {
            swap(matrix[y2][i - 1], prevValue);
            minValue = min(minValue, prevValue);
        }
        
        // 위로
        for (int i = y2; i > y1; --i)
        {
            swap(matrix[i - 1][x1], prevValue);
            minValue = min(minValue, prevValue);
        }
        
        answer.push_back(minValue);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \times m + q \times (n + m))$입니다.

• 2차원 배열을 초기화하는 반복문 $O(n \times m)$
• 쿼리를 처리하는 반복문 $O(q \times (n + m))$
  • q는 쿼리의 개수
• $O(n \times m + q \times (n + m))$

공간 복잡도는 $O(n \times m + q)$입니다.

• 2차원 배열을 저장하는 vector<vector<int>> matrix $O(n \times m)$
• 결과를 저장하는 vector<int> answer $O(q)$
• $O(n \times m + q)$

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (3.01ms, 6.32MB)
테스트 4 〉 통과 (2.13ms, 5.56MB)
테스트 5 〉 통과 (2.39ms, 5.18MB)
테스트 6 〉 통과 (3.66ms, 6.7MB)
테스트 7 〉 통과 (4.10ms, 7.2MB)
테스트 8 〉 통과 (2.33ms, 5.79MB)
테스트 9 〉 통과 (3.25ms, 6.75MB)
테스트 10 〉 통과 (5.00ms, 6.3MB)
테스트 11 〉 통과 (4.32ms, 5.97MB)