[ 프로그래머스 ] 행렬과 연산 (C++)

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

 

 행의 길이와 열의 길이가 최대 50000,  행*열이 최대 1000000,  operation의 개수가 최대 100000이므로

ShiftRow와 Rotate 연산을 수행하는데 걸리는 시간복잡도는 O(log n)이어야 한다.

 

 따라서,

vector를 사용할 수 없고(맨 뒤에 원소 삽입, 삭제: O(1), 맨 앞의 원소 삭제: O(n))

deque를 사용해 연산을 수행한 뒤(맨 앞, 뒤에 원소를 삽입, 삭제: O(1)) 마지막에 모든 연산을 수행한 결과를 2차원 vector로 옮겨 반환해야 한다.

 

 ShiftRow 연산의 경우,

 모든 열을 deque에 옮겨 순서를 바꾸는 것은 비효율적이고,

 Rotation 연산을 수행할 때는 열이 아닌 맨 위와 아래의 행이 필요하기 때문에 ShiftRow 연산을 수행할 때마다 맨 위와 아래의 행을 2차원 배열이나 행을 저장하는 deque에 업데이트 해주어야 하므로 시간초과가 발생할 것이라 생각했다.

 

 따라서 가장 왼쪽(l)과 오른쪽의 열(r)만 deque로 저장해 연산을 수행하고, 나머지 열의 경우 연산을 수행한 뒤 가장 위에 있어야 하는 행의 index를 저장해주는 식으로 구현했다.

topIdx = (topIdx + rc.size() - 1) % rc.size();

 

 

 Rotate 연산의 경우,

 가장 왼쪽과 오른쪽의 열을 저장해둔 deque(l, r)와 현재 가장 위에 있어야 하는 행의 index(topIdx)를 이용해 구현했다.

 처음엔 topIdx와 bottomIdx((topIdx + rc.size() - 1) % rc.size()))를 이용해 Rotate 연산을 수행할 때마다 top과 bottom 행의 원소를 저장하는 deque를 생성하고 이용하여 회전을 구현하였으나 시간초과가 발생했다.

 

=> top과 bottom 행을 deque로 생성하는 시간 때문이라고 생각해 처음부터 모든 행(가장 왼쪽과 오른쪽을 제외한)을 저장하는 deque의 배열을 만들어 사용하도록 수정했고 시간초과를 해결할 수 있었다.

 

 그러나 Segment fault가 발생했고, 디버깅하다가 열이 2개인 2차원 배열이 주어질 경우 bottom 행의 첫 원소를 left 열의 마지막 원소로 추가하는 부분에서 에러가 발생함을 알 수 있었고(bottom deque가 비어있기 때문), 열이 2개인 경우에는 l과 r deque만 사용하여 Rotate를 수행하도록 수정하여 문제를 해결할 수 있었다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

void shiftRow(deque<int>& l, deque<int>& r, int& topIdx) {
    int size = int(l.size());
    topIdx = (topIdx+size-1) % size;
    
    int t = l.back();
    l.pop_back();
    l.push_front(t);
    
    t = r.back();
    r.pop_back();
    r.push_front(t);
}

void rotate(deque<int>& l, deque<int>& r, vector<deque<int>>& rows, int& topIdx) {
    
    int size = int(l.size());
    int botIdx = (topIdx+size-1)%size;
    
    int t = l.front();
    l.pop_front();
    
    if(rows[topIdx].size() > 0) {
        l.push_back(rows[botIdx].front());
        rows[botIdx].pop_front();
        
        rows[botIdx].push_back(r.back());
        r.pop_back();
        
        r.push_front(rows[topIdx].back());
        rows[topIdx].pop_back();
        
        rows[topIdx].push_front(t);
    } else {
        l.push_back(r.back());
        r.pop_back();
        
        r.push_front(t);
    }
}

vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
    vector<vector<int>> answer(rc.size(), vector<int>());
    
    deque<int> l;
    deque<int> r;
    vector<deque<int>> rows(rc.size());
    
    int topIdx = 0;
    
    for(int i = 0; i < rc.size(); i++) {
        l.push_back(rc[i].front());
        r.push_back(rc[i].back());
    }
    
    for (int i = 0; i < rc.size(); i++) {
        for (int j = 1; j < rc[i].size()-1; j++) {
            rows[i].push_back(rc[i][j]);
        }
    }
    
    for (int i = 0; i < operations.size(); i++) {
        string s = operations[i];
        if (s == "ShiftRow") {
            shiftRow(l, r, topIdx);
        } else {
            rotate(l, r, rows, topIdx);
        }
    }
    
    for (int i = 0; i < rc.size(); i++) {
        for (int j = 0; j < rc[i].size(); j++) {
            if(j == 0) {
                answer[i].push_back(l.front());
                l.pop_front();
            } else if(j == rc[i].size()-1) {
                answer[i].push_back(r.front());
                r.pop_front();
            } else {
                answer[i].push_back(rows[(topIdx+i)%rc.size()].front());
                rows[(topIdx+i)%rc.size()].pop_front();
            }
        }
    }
    
    return answer;
}

 

 더 좋은 방법이 없을까 해서 다른 사람들의 풀이 방법을 보다가, Rotate를 구현할 때 순서만 잘 설정해주면 열이 2개인 경우에도 에러가 발생하지 않는다는 것을 깨달았다.

 다음과 같은 순서로 Rotate를 구현하면 Segment fault가 발생하지 않는다.

void rotate(deque<int>& l, deque<int>& r, vector<deque<int>>& rows, int& topIdx) {
    
    int size = int(l.size());
    int botIdx = (topIdx+size-1)%size;
    
    int t = l.front();
    l.pop_front();
    
    rows[botIdx].push_back(r.back());
    r.pop_back();
    
    l.push_back(rows[botIdx].front());
    rows[botIdx].pop_front();
    
    rows[topIdx].push_front(t);
    
    r.push_front(rows[topIdx].back());
    rows[topIdx].pop_back();
}