알고리즘 문제풀이
[Programmers] 프로그래머스 Lv.4 행렬과 연산 문제풀이(C++) - 2022 KAKAO TECH INTERNSHIP
도리컴
2023. 9. 27. 02:15
반응형
deque를 이용한 연산을 하는 것이 핵심이고,
내가 느낀 어려웠던 점은
1. 2*2 행렬에서 segmentation fault를 일으켰었는데, Rotate연산에서 mid값을 먼저 참조하지 않도록 해야 한다.
2. 7번 8번 테케에서 시간초과가 떴는데, mid를 deque<deque<int> * >로 설정해야 한다(복사연산으로 인한 시간초과 발생)
등이 있었다.
솔직히 문제 보면서 2시간 정도 고민했는데, 방법을 떠올리지 못했었다. 이후 풀이를 살짝 봤는데, deque라는 단어만 보고 다시 구현해보다가 위에 언급한 2개 문제 해결하면서 또 시간 어마어마하게 날려먹었다.
Lv.4 앞으로 좀 많이 익숙해질 필요가 있겠다.
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
#include <string>
#include <vector>
#include <deque>
using namespace std;
/*
<문제>
행렬 연산 - ShiftRow, Rotate연산을 하려 함
행렬초기상태 rc (2차원 정수배열), operations(시행할 연산 순서 - 문자열 배열) 주어졌을 때,
연산을 차례대로 시행한 후의 행렬상태를 return
rc 행 길이(=열 길이) <= 5만
rc 행 * 열 <= 10만
rc[i][j]는 i+1번째행 j+1번째 열에 있는 원소를 의미 / 각 원소 100만 이하
operations 길이 <= 10만 / 모두 "ShiftRow 또는 Rotate"
<풀이>
1. 핵심은 deque - 양방향에서 삽입/삭제 가능한 큐
2. 배열의 좌우 및 중간 행렬을 모두 deque로 구현
-> shift 시 위/아래 deque만 모두수정, 좌우는 처음과 끝만 수정 -> O(행 길이 * 2)
-> rotate 시 deque들만 삽입/삭제 하면 됨 -> O(1)
3. up, down 필요없이 그냥 left / right / mid 로만 구성
front/back도 굳이 시계방향 필요없이 위에서 아래로 정함
* segmentation falut 문제발생 : Rotate연산 순서 변경으로 해결 - 2*2의 경우 나는 에러였음
* 7, 8번 테스트케이스 시간초과 : mid를 deque 포인터로 자료구조 변경해서 해결 - 포인터로 안할 시, 복사연산이 일어남으로 인한 시간초과
<시간>
O(NM + Q)
*/
vector<vector<int>> answer;
deque<int> right, left;
deque<deque<int> * > mid; //포인터형
deque<deque<int> > middle;
void Rotate() { //회전 - middle값 을 먼저 참조하면 2*2배열에서 segmentation falut
mid.front()->push_front(left.front()); left.pop_front(); //왼쪽거 떼서 위로
right.push_front(mid.front()->back()); mid.front()->pop_back(); //위쪽거 떼서 오른쪽으로
mid.back()->push_back(right.back()); right.pop_back(); //오른쪽거 떼서 아래쪽으로
left.push_back(mid.back()->front()); mid.back()->pop_front(); //아래쪽거 떼서 왼쪽으로
}
void ShiftRow() { //한칸 내리기 - 포인터 이용 안하면 시간초과 발생
//왼쪽부분
left.push_front(left.back()); left.pop_back();
//오른쪽부분
right.push_front(right.back()); right.pop_back();
//중간부분
mid.push_front(mid.back()); mid.pop_back();
}
void getAnswer() { //정답 조합하기
for (int i = 0; i < left.size(); i++) {
vector<int> ans;
//왼쪽부분
ans.push_back(left[i]);
//중간부분
for (int j = 0; j < mid[i]->size(); j++)
ans.push_back(mid[i]->at(j));
//오른쪽부분
ans.push_back(right[i]);
//한줄 완료
answer.push_back(ans);
}
}
vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
//여러번 호출 대비 초기화
answer.clear(); right.clear(); left.clear(); middle.clear();
//rc보면서 left, right, mid 채우기
for (int i = 0; i < rc.size(); i++) {
right.push_back(rc[i][rc[0].size() - 1]);
left.push_back(rc[i][0]);
deque<int> * m = new deque<int>;
for (int j = 1; j < rc[0].size() - 1; j++) {
m->push_back(rc[i][j]);
}
mid.push_back(m);
}
//연산 수행
for (int i = 0; i < operations.size(); i++){
if (operations[i][0] == 'R')
Rotate();
else if (operations[i][0] == 'S')
ShiftRow();
}
getAnswer();
return answer;
}
/*
<의식의 흐름> - 안보셔도 됩니다
ShiftRow - O(행길이)
-> 각 행을 가리키는 포인터로 가야할 듯? -> 큐
Rotate - O(행길이)
그대로 구현하면? - O(행길이 * 10만) -> 약 5만*10만 -> 50억
2차원 배열 생성
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
ShiftRow
start_row = 0 / 시작배열 유지 - ShiftRow 시, 하나씩만 올려주면 됨( % 행 길이 )
Rotate
start
Rotate에 바뀌는 값들을 시계방향 순서대로 배열에 담고있으면?
rotate_list = {1, 2, 3, 6, 9, 8, 7, 4}
-> ShiftRow마다 이걸 수정해주면? -> 식 세워서 빨리 바꿀 수 있을듯?
ShiftRow 1회 시 rotate_list의 변화
총 길이 : 2*r + 2*c - 4 => r_size로 설정
(rc[r-1][0] ~ rc[r-1][c-1]까지) + (rotate_list[c] ~ [c+r-2]까지) +
(rc[r-2][c-2] ~ rc[r-2][1]까지) + rotate_list[r_size-1-(r-2)] ~ [r_size-1]까지)
-> 이렇게 rotate_list를 구성하면 ShiftRow를 한 번 실행한 결과가 됨
ShiftRow
rotate_list 변화
start_row +1 % r
Rotate
rotate_list 밀기 -> start_rotate로 관리?
Answer 계산
각 row랑 rotate_list 적절히 배치해서 push
rotate_list랑 아예 분리해서 rc를 따로 가지면? - 겉에 한바퀴랑, 속에 직사각형 배열들을 아예 따로 관리
- 그러면 Rotate 시 rotate_list만 밀면 됨
각 배열 위치마다 상하로 몇번, 좌우로 몇번 이동하는지에 대한 누적합을 구하면?
지금의 문제 : rotate와 shift를 독립적으로 나눌 수가 없음
- 그냥 구현하면 어떻게 될지도 모르겠음 / 그냥 되는거 아니겠지?
* 결국 해설 봤음(정답에 대한 힌트를 얻음)
핵심이 deque라고 함 - 양방향에서 삽입/삭제 가능한 큐
배열의 상하좌우 행/렬을 모두 deque로 구현
-> shift 시 위/아래 deque만 모두수정, 좌우는 처음과 끝만 수정 -> O(행 길이 * 2)
-> rotate 시 deque들만 삽입/삭제 하면 됨 -> O(1)
up, down 필요없이 그냥 left / right / mid 로만 구성
front/back도 굳이 시계방향 필요없이 위에서 아래로 정함
* segmentation falut 문제발생 : Rotate연산 순서 변경으로 해결
* 7, 8번 테스트케이스 시간초과 : deque 포인터로 자료구조 변경해서 해결
*/
|
cs |
반응형