[2022 KAKAO TECH INTERNSHIP] 행렬과 연산

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/118670

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 deque 자료구조를 이용하여 풀 수 있습니다. 이 문제는 일반적인 방법으로 완전탐색하게 된다면 시간 초과가 발생합니다. 따라서 시간 초과를 일어나지 않도록 하는 아이디어가 필요합니다. 여기서 deque를 이용하면 값 추가 및 삭제 시 O(1)로 크게 시간을 줄일 수 있다는 점을 이용하여 문제를 접근하면 됩니다.

우선 문제에 주어진 행렬을 크게
1. 제일 처음의 수
2. 가운데 수
3. 제일 마지막 수

의 3가지의 deque로 나눕니다. 이렇게 나누게 되면 ShiftRow 작업과 Rotate 작업은 다음의 로직대로 진행됩니다.

ShiftRow
위의 3개의 deque의 제일 마지막 값을 제일 앞에 추가한다

Rotate
1. 제일 처음의 수의 deque의 제일 앞의 값을 가운데 수의 deque의 제일 위의 앞에 추가
2. inner의 제일 앞의 뒤의 값을 제일 마지막의 수의 deque의 제일 위의 앞에 추가
3. 제일 마지막의 수의 deque의 제일 뒤의 값을 inner의 제일 뒤의 뒤에 추가
4. 가운데 수의 deque의 제일 뒤의 앞의 값을 제일 처음의 수의 deque의 제일 뒤에 추가

다음은 코드입니다.

import java.util.*;

class Solution {
    // 제일 앞의 값, 제일 뒤의 값, 가운데 값 저장
    static Deque<Integer> first = new LinkedList<>();
    static Deque<Integer> last = new LinkedList<>();
    static Deque<Deque<Integer>> inner = new LinkedList<>();
    
    // 제일 밑의 값을 제일 앞으로 이동
    static void shiftRow(){
        first.addFirst(first.pollLast());
        inner.addFirst(inner.pollLast());
        last.addFirst(last.pollLast());
    }
    
    // first의 제일 앞의 값을 inner의 제일 위의 앞에 추가
    // inner의 제일 앞의 뒤의 값을 last의 제일 위의 앞에 추가
    // last의 제일 뒤의 값을 inner의 제일 뒤의 뒤에 추가
    // inner의 제일 뒤의 앞의 값을 first의 제일 뒤에 추가
    static void rotate(){
        inner.getFirst().addFirst(first.pollFirst());
        last.addFirst(inner.getFirst().pollLast());
        inner.getLast().addLast(last.pollLast());
        first.addLast(inner.getLast().pollFirst());
    }
    
    public int[][] solution(int[][] rc, String[] operations) {
        // rc의 데이터 저장
        for(int i=0;i<rc.length;i++){
            Deque<Integer> deq = new LinkedList<>();
            
            first.add(rc[i][0]);
            for(int j=1;j<rc[i].length-1;j++) deq.add(rc[i][j]);
            inner.add(deq);
            last.add(rc[i][rc[i].length-1]);
        }
        
        // operations 개수에 따라 명령 실행
        for(int i=0;i<operations.length;i++){
            String cmd = operations[i];
            
            if(cmd.equals("ShiftRow")) shiftRow();
            if(cmd.equals("Rotate")) rotate();
        }
        
        // 정답 출력
        int[][] answer = new int[rc.length][rc[0].length];
        int idx = 0;
        while(!first.isEmpty()){
            answer[idx][0] = first.pollFirst();
            idx++;
        }
        idx = 0;
        while(!inner.isEmpty()){
            Deque<Integer> deq = inner.pollFirst();
            int i = 1;
            while(!deq.isEmpty()){
                answer[idx][i] = deq.pollFirst();
                i++;
            }
            idx++;
        }
        idx = 0;
        while(!last.isEmpty()){
            answer[idx][rc[0].length-1] = last.pollFirst();
            idx++;
        }
        
        return answer;
    }
}