[프로그래머스/C++] 행렬과 연산 (2022 KAKAO TECH INTERNSHIP)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 어떻게 효율적으로 연산을 하는지가 중요한 문제다.

먼저 처음에는 단순하게 구현했다. 구현 결과 회전의 경우 값 자체를 직접 변경해줬기 때문에 시간 초과가 걸렸다.

 

그래서 deque를 이용해 push 와 pop을 빠르게 연산 할 수 있도록 코드를 짰다. 

shift연산의 경우 단순히 deque의 push와 pop을 이용하면 되기 때문에 쉽게 코드를 구현할 수 있었다.

 

하지만 rotation의 경우 오른쪽은 아래로 왼쪽은 위로 값들이 바뀌기 때문에 구조를 분리할 필요가 있었다.

위와 아래의 경우 값을 단순히 2차원 deque의 처음과 끝에 push와 pop을 적절히 사용하면 되기 때문에 따로 분리하지 않아도 쉽게 해결할 수 있었다.

 

오른쪽과 왼쪽의 경우는 1차원의 deque를 만들어 push와 pop연산을 빠르게 할 수 있도록 구현해 문제를 해결했다.

이렇게 하면 모든 값들을 직접 옮기지 않고 1번의 pop과 1번의 push만으로 문제를 해결할 수 있게 된다.

 

하지만 이렇게 문제를 풀어도 효율성 테스트에서 7번을 통과하지 못했다...

 

rotation과 shift가 연속으로 일어날 경우를 파악해 %연산으로 수를 줄여도 보고 deque를 한번에 삽입하는 erase와 insert를 이용해보기도 했다.

 

하지만 그래도 해결되지 않았는데, 알고보니 deque에 push를 하는 동안 값이 복사가 돼 효율성이 떨어지는 문제가 있었다...

2차원 deque에 값을 push할 때 deque<int>의 값들이 전부 복사가 되고 있었고, 이 때문에 push를 하는 부분에서 효율성이 떨어졌다.

 

그래서 코드를 deque<int>의 주소를 저장하도록 deque<deque<int>*>로 코드를 수정했고, 통과할 수 있었다.

 

 

[아이디어 정리]

1. deque를 이용해 push와 pop연산을 빠르게 할 수 있도록 코드를 구현한다.
2. 이때, rotation에서 오른쪽과 왼쪽은 push와 pop을 하기 위해 따로 1차원 deque<int>로 만든다.
3. deque에 push를 하는 연산에서 복사가 일어나 연산속도가 떨어지므로 포인터를 이용해 copy가 일어나지 않도록 deque<deque<int>*>를 사용한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <deque>
using namespace std;

int dx,dy;
deque<int> leftD, rightD; 

void shift(deque<deque<int>*> &dq)
{    
    // 왼, 오른쪽 동기화
    leftD.push_front(leftD.back());
    leftD.pop_back();    
    rightD.push_front(rightD.back());
    rightD.pop_back();

    dq.push_front(dq.back());
    dq.pop_back();

    // 동기화
    dq[dy]->back()=rightD.back(), dq[dy]->front()=leftD.back();
    dq[0]->back()=rightD.front(), dq[0]->front()=leftD.front();  
}

void rotate(deque<deque<int>*> &dq)
{
    leftD.pop_front();
    dq[0]->pop_back(), dq[0]->push_front(leftD.front());
    rightD.pop_back(), rightD.push_front(dq[0]->back());    
    dq[dy]->pop_front(),dq[dy]->push_back(rightD.back()); 
    leftD.push_back(dq[dy]->front());
}

vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
    dy=rc.size()-1;
    dx=rc[0].size()-1;
    deque<int> ddq[dy+1];
    deque<deque<int>*> dq;    
    for (int i=0; i<rc.size(); i++)
    {
        dq.push_back(new deque<int>(rc[i].begin(),rc[i].end()));
    }
    for (int i=0; i<dq.size(); i++)
    {
        leftD.push_back(dq[i]->front());
        rightD.push_back(dq[i]->back());
    }
    for (int i=0; i<operations.size(); i++)
    {
        if (operations[i]=="Rotate")
        {
            rotate(dq);
        }
        else
        {
            shift(dq);
        }
    }
    
    for (int i=0; i<=dy; i++)
    {
        dq[i]->front()=leftD[i],dq[i]->back()=rightD[i];   
    }    
    vector<vector<int>> answer;
    for (int i=0; i<=dy; i++)
    {
        answer.push_back(vector<int>(dq[i]->begin(),dq[i]->end()));
    }
    return answer;
}

 

---

 

예전에도 비슷한 경험이 있었는데, 그때는 함수에 인자를 전달하는 과정에서 copy가 계속 일어나 코드가 시간초과가 일어났었다...

이번에는 deque에 push하는 과정에서 복사가 일어나서 시간초과가 났는데 이유를 알기까지 너무 오랜 시간이 걸렸다;;

아오...

프로그래머스