(프로그래머스) 2022 KAKAO TECH INTERNSHIP - 행렬과 연산 [C++]
사용한 자료구조
Deque
deque는 특수한 vector라고 생각하면 된다. vector는 상수 시간에 지원되는 연산이 push_back, pop_back이다. 그러나 deque는 push_front,push_back,pop_front,pop_back을 상수 시간에 지원된다.
vector는 push_back이 amortized O(1), pop_back은 O(1)이다. deque는 push_front, push_back, pop_front, pop_back을 모두 O(1)에 지원한다.
그럼 “왜 항상 deque만 쓰지 않고 vector를 쓸까?” 하는 의문이 생긴다. 이유는 인덱스 접근 속도 때문이다.
이론적으로 vector[i]와 deque[i] 모두 O(1)이지만, • vector는 메모리가 연속적이라 단순 덧셈 연산으로 바로 접근 가능하고 캐시 효율이 높다. • deque는 블록 구조라서 index 계산에 나눗셈, 포인터 간접 참조가 필요하고, 원소가 흩어져 있어 캐시 효율이 낮다.
따라서 실제 성능에서는 vector가 deque보다 인덱스 접근이 더 빠르다.
이번 문제를 풀때 push_back,push_front,pop_back,pop_front가 빈번하게 사용되기 때문에 deque를 사용했다.
틀린 풀이 #1
처음 문제를 풀었을 때, Rough하게 문제를 풀었지만 당연히 시간 복잡도 측면에서 Pass가 되지 않았다. 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <string>
#include <vector>
using namespace std;
vector<vector<int>> shiftRow(vector<vector<int>> rc) { //call by reference
for (int i = (int)rc.size()-1; i > 0; i--) {
for (int j = 0; j < (int) rc[i].size(); j++) {
swap(rc[i][j], rc[i-1][j]);
}
}
return rc;
}
vector<vector<int>> rotate(vector<vector<int>>rc){
vector<vector<int>>rcCopy = rc; //rc의 복사본
int i,j;
//1
i = 0;
for( j =0;j<=(int)rc[0].size()-2;j++){
rcCopy[0][j+1] = rc[0][j];
}
//2
for( i=0;i<=(int)rc.size()-2;i++){
j = rc[i].size()-1;
rcCopy[i+1][j] = rc[i][j];
}
//3
i = rc.size()-1;
for(j=(int)rc[i].size()-1;j>=1;j--){
rcCopy[i][j-1] = rc[i][j];
}
//4
j = 0;
for(int i=(int)rc.size()-1;i>=1;i--){
rcCopy[i-1][j] = rc[i][j];
}
return rcCopy;
}
vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
//연산자 백터 검사
for (int i = 0; i < (int) operations.size(); i++) {
string operation = operations[i];
//ShitftRow 구현;
if (operation == "ShiftRow") {
rc = shiftRow(rc);
}
else if(operation =="Rotate"){ //else로 치환해도 무방
//Rotate 구현
rc = rotate(rc);
}
}
return rc;
}
rc vector를 그대로 copy하고 있기 때문에 공간 복잡도 효율도 많이 떨어지는 코드이다.
deque를 사용한 풀이법
Divide into thirds
입력으로 들어온 RC vector을 그림과 같이 3등분한다. (그림이 안 이쁜거는 감안하자.) 
코드상으로는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
deque<int> leftColumn, rightColumn;
deque<deque<int> *> middles;
// 초기 분리
for (int i = 0; i < rows; i++) {
leftColumn.push_back(rc[i][0]);
rightColumn.push_back(rc[i][cols - 1]);
deque<int> mid;
for (int j = 1; j < cols - 1; j++) mid.push_back(rc[i][j]);
middles.push_back(&mid);
}
ShiftRow
ShiftRow는 구현이 쉽다. 3등분된 각각의 부분들을 pop_back(),pop_front()연산을 취해주면 된다.
left의back을left의front에push하고 ,left의back을pop한다.middle의back을middle의front에push하고 ,middle의back을pop한다.right의back을right의front에push하고 ,right의back을pop한다.
그림으로는 다음과 같다. 
코드상으로는 다음과 같다.
1
2
3
4
5
6
leftColumn.push_front(leftColumn.back());
leftColumn.pop_back();
rightColumn.push_front(rightColumn.back());
rightColumn.pop_back();
middles.push_front(middles.back());
middles.pop_back();
Rotate
Rotate가 가장 어려운 부분이다. 이 문제에서 Rotate는 rc의 둘레에 있는 값들이 시계방향으로 회전한다.
움직임을 고려해야하는 점들을 생각해보자.
(0,0)=left.front()(0,1)=middle.front().front()(0,C-1)=middle.front().back()(0,C)=right.front()(R,0)=left.back()(R,1)=middle.back().front()(R,C-1)=middle.back().back()(R,C)=right.back()
나는 phase 1~4로 나누어 설명을 진행하고자 한다.
phase 1
1) left의 front을 middle의 front의 front에 push한다.
2) left의 front를 pop한다
그림으로는 다음과 같다.
코드로는 다음과 같다.
1
2
middles.front()->push_front(leftColumn.front());
leftColumn.pop_front();
## phase 2
1) middle의 front의 back을left의 front에 push한다.
2) middle의 front의 back을 pop 한다.
그림으로는 다음과 같다.
코드로는 다음과 같다.
1
2
rightColumn.push_front(middles.front()->back());
middles.front()->pop_back();
phase 3
1) right의 back을 middle의 back의 back에 push한다.
2) right의 back을 pop한다.
그림으로는 다음과 같다. (그림에 오타가 있습니다. left->right) 
코드로는 다음과 같다.
1
2
middles.back()->push_back(rightColumn.back());
rightColumn.pop_back();
phase 4
1) middle의 back의 front를 left의 back에 push한다.
2) middle의 back의 front를 pop한다.
그림으로는 다음과 같다. 
코드로는 다음과 같다.
1
2
leftColumn.push_back(middles.back()->front());
middles.back()->pop_front();
이로써 phase 1~4까지 진행하면 한번의 Rotate의 연산이 마무리 된다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <string>
#include <vector>
#include <deque>
using namespace std;
vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
int rows = rc.size();
int cols = rc[0].size();
deque<int> leftColumn, rightColumn;
deque<deque<int> *> middles;
// 초기 분리
for (int i = 0; i < rows; i++) {
leftColumn.push_back(rc[i][0]);
rightColumn.push_back(rc[i][cols - 1]);
deque<int> mid;
for (int j = 1; j < cols - 1; j++) mid.push_back(rc[i][j]);
middles.push_back(&mid);
}
for (auto &op: operations) {
if (op == "ShiftRow") {
leftColumn.push_front(leftColumn.back());
leftColumn.pop_back();
rightColumn.push_front(rightColumn.back());
rightColumn.pop_back();
middles.push_front(middles.back());
middles.pop_back();
} else { // Rotate
if (cols == 2) { // 중간 없음
rightColumn.push_front(leftColumn.front());
leftColumn.pop_front();
leftColumn.push_back(rightColumn.back());
rightColumn.pop_back();
} else {
// phase1: left → top middle
middles.front()->push_front(leftColumn.front());
leftColumn.pop_front();
// phase2: top middle → right
rightColumn.push_front(middles.front()->back());
middles.front()->pop_back();
// phase3: right → bottom middle
middles.back()->push_back(rightColumn.back());
rightColumn.pop_back();
// phase4: bottom middle → left
leftColumn.push_back(middles.back()->front());
middles.back()->pop_front();
}
}
}
// 합치기
vector<vector<int>> result(rows, vector<int>(cols));
for (int i = 0; i < rows; i++) {
result[i][0] = leftColumn.front();
leftColumn.pop_front();
auto &mid = middles.front();
for (int j = 1; j < cols - 1; j++) {
result[i][j] = mid->front();
mid->pop_front();
}
middles.pop_front();
result[i][cols - 1] = rightColumn.front();
rightColumn.pop_front();
}
return result;
}
느낀점
정확성 테스트는 문제없이 통과하는데 시간초과에서 삽질을 많이 한 것 같다. 어떻게 하면 효율적으로 연산을 수행할지에 대한 고민을 많이 했다.