[프로그래머스] 행렬과 연산

문제 설명

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

문제 풀이

• Deque는 이용했지만 아이디어에 한계의 부딪혀 풀이를 참조하였다.
• 자료구조를 극한으로 활용하는 문제가 아닐까 싶다.
• 다음 그림과 같이 행렬을 분해한다.
• 
• 왼쪽 칼럼 Deque(이하 leftCol), 오른쪽 칼럼 Deque(이하 rightCol), 왼쪽 오른쪽 사이 원소 중 각 row를 Deque, 각 row Deque를 원소로 하는 Deque(이하 rows) 크게 총 4가지 Deque가 존재한다.
• operation 별 로직은 다음과 같다.

  1. ShiftRow
     • 가운데 원소들 : rows를 한칸씩 밀어준다.
     • 왼쪽 칼럼 원소들 : leftCol을 한칸씩 밀어준다.
     • 오른쪽 칼럼 원소들 : rightCol을 한칸씩 밀어준다.
  2. Rotaton
     • leftCol -> TopDeque(위 그림 2,3,4) : leftCol first를 빼서 TopDeque의 first에 넣는다.
     • TopDeque -> rightCol : TopDeque Last를 빼서 rightCol의 first에 넣는다.
     • rightCol -> BottomDeque(위 그림 12,13,14) : rightCol의 Last를 빼서 BottomDeque Last에 넣는다
     • BottomDeque -> leftCol : BottomDeque First를 빼서 leftCol의 Last에 넣는다.

소스 코드 (JAVA)

import java.util.*;
class Solution {
    public int[][] solution(int[][] rc, String[] operations) {
        //초기화
        int R = rc.length;
        int C = rc[0].length;
        ArrayDeque<Integer> leftCol = new ArrayDeque<>();
        ArrayDeque<Integer> rightCol = new ArrayDeque<>();
        ArrayDeque<ArrayDeque<Integer>> rows = new ArrayDeque<>();
        for (int i = 0; i < R; i++) {
            leftCol.add(rc[i][0]);
            rightCol.add(rc[i][C-1]);
            ArrayDeque<Integer> tmp = new ArrayDeque<>();
            for (int j = 1; j < C-1; j++)
                tmp.add(rc[i][j]);
            rows.add(tmp);
        }

        //연산 수행
        for (String op : operations) {
            //ShiftRow
            if (op.charAt(0) == 'S') {
                leftCol.addFirst(leftCol.removeLast());
                rightCol.addFirst(rightCol.removeLast());
                rows.addFirst(rows.removeLast());
            }
            //Rotate
            else {
                //left -> top
                rows.getFirst().addFirst(leftCol.removeFirst());
                //top -> right
                rightCol.addFirst(rows.getFirst().removeLast());
                //right -> bottom
                rows.getLast().addLast(rightCol.removeLast());
                //bottom -> left
                leftCol.addLast(rows.getLast().removeFirst());
            }
        }

        int[][] result = new int[R][C];
        for (int i = 0; i < R; i++) {
            result[i][0] = leftCol.removeFirst();
            result[i][C-1] = rightCol.removeFirst();
            ArrayDeque<Integer> tmp = rows.removeFirst();
            for (int j = 1; j < C-1; j++)
                result[i][j] = tmp.removeFirst();
        }

        return result;
    }
}