[2022 KAKAO TECH INTERNSHIP] 행렬과 연산

[uijin-j]

🔗 행렬과 연산

[hye-on]

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include using namespace std; //06:40 // 7:40~8:20 //vector> rc; int n,m; vector> solution(vector> rc, vector operations) { dequeleft; dequeright; deque>pipe; n = rc.size(); m = rc[0].size(); vector> answer(n,vector(m,0)); pipe.resize(n); for(int i=0;i

코멘트

- m=2일 떄 엣지케이스를 생각하기 어려웠고 자료구조 활용할 방법이 생각이 안났었네요..

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.*; // 16:05 START 17:30 class Solution { /** * 무식한 방법 O(n^2c) ~= 10_000_000_000 시간 초과 * * 시간을 줄일 수 있는 방법? 연산을 할 때 모든 칸을 돌지 않으면 됨! * ShiftRow의 경우에는 직접 원소를 옮기는 것이 아니라, 어떤 열의 순서만 알면됨! (큐 사용하기) * Rotate는 바깥쪽 행/열을 큐로 구현하면 O(1)로 가능함 * * 1 2 3 4 * 5 6 7 8 * 9 10 11 12 * 13 14 15 16 */ public int[][] solution(int[][] rc, String[] operations) { int n = rc.length; int m = rc[0].length; System.out.println(n + " " + m); Deque firstCol = new ArrayDeque<>(); Deque lastCol = new ArrayDeque<>(); Deque> rows = new ArrayDeque<>(); for(int row = 0; row < n; ++row) { firstCol.offerLast(rc[row][0]); lastCol.offerLast(rc[row][m-1]); Deque deque = new ArrayDeque<>(); for(int col = 1; col < m - 1; ++col) deque.offerLast(rc[row][col]); rows.offerLast(deque); } for(int i = 0; i < operations.length; ++i) { String operation = operations[i]; if(operation.equals("ShiftRow")) { rows.offerFirst(rows.pollLast()); firstCol.offerFirst(firstCol.pollLast()); lastCol.offerFirst(lastCol.pollLast()); } if(operation.equals("Rotate")) { if (m == 2) { lastCol.addFirst(firstCol.pollFirst()); firstCol.addLast(lastCol.pollLast()); continue; } Deque firstRow = rows.peekFirst(); Deque lastRow = rows.peekLast(); firstRow.addFirst(firstCol.pollFirst()); lastCol.addFirst(firstRow.pollLast()); lastRow.addLast(lastCol.pollLast()); firstCol.addLast(lastRow.pollFirst()); } } int[][] answer = new int[n][m]; for(int row = 0; row < n; ++row) { answer[row][0] = firstCol.pollFirst(); answer[row][m-1] = lastCol.pollFirst(); Deque deque = rows.pollFirst(); for(int col = 1; col < m - 1; ++col) answer[row][col] = deque.pollFirst(); } return answer; } } ```

코멘트

- 단순 구현 문제같았는데, 역시나 시초가 나네요..
- 명령어의 수는 절대적인 값이기 때문에, 각 명령어를 O(1) 또는 O(logn)으로 해결해야 했습니다! 단순히 로우만 바꿔주는 것은 아이디어가 쉽게 떠올랐는데.. 회전하는건 도저히 O(n)이 아니게는 못하겠더라구요ㅜㅜ 정답을 찾아보니 회전이 쉽도록 각 영역을 적절하게 나눠서 큐를 사용하는 문제였습니다.!