[프로그래머스,Java] Level4: 행렬과 연산

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

프로그래머스

문제분석

 

문제 목표 :   Shift 연산과  Rotate연산을 수행하여 행렬 출력하기

 

 

Shift 연산 = 맨 아래행을   첫번째 행으로 이동

 

Rotate연산 = 테두리부분의 원소를 시계방향으로 회전

 

 

기능 구현은 매우 쉽다 !   하지만 이 문제는 정확도 점수 25점: 효율성 점수 75점이다!

 

그 중에도 효율성의 75점중 50점인 부분은 매우매우 빡센 효율성을 만족해야만한다.

 

 

 

결론부터 말하자면 Rotate 연산과 Shift연산이 시간복잡도가 O(1)이여야한다.

 

어떻게 O(1)을하나??

 

 

다음과같이 행렬을 쪼갠다.   양쪽 사이드에 리스트 하나씩,  중간에 이중리스트 한개 총 3개를 구별해서 관리한다.

 

이렇게 관리를하면  Rotate연산은  단 4번만 움직이면 회전연산이된다.

 

1. 왼쪽기둥 1번원소 뽑아서  내부 1번째행 맨앞에 추가

2. 내부 1번째행 맨뒤원소 뽑아서  오른쪽기둥 1번자리에 추가

3. 오른쪽기둥 마지막 원소 뽑아서 내부 마지막행 마지막번째에 추가

4.내부 마지막행 첫번째원소 뽑아서 왼쪽기둥 마지막자리에 추가

 

 

 

다음은 Shift연산이다. 

 

Shift연산은 

1. 왼쪽기둥 마지막 원소를 첫번째로,

2. 내부 기둥 마지막 행을 첫번째행으로

3. 오른쪽 기둥 마지막 원소를 첫번째로

 

 

 

문제는 이 행동을 했을때 자신도 모르게 O(N)연산을 써버릴수가 있다는것이다.

 

LinkedList를 썻을때를 들어보겠다.   삽입 ,삭제는 O(1)연산이 걸리지만  get()연산은 O(N)이다.

 

즉, 마지막 원소를 찾아서 첫번째 원소로 보낸다는행위를 LinkedList로 하면,

 

get(마지막) ,  add(첫번째)  식일텐데,  저 get()에서 O(N)이 걸린다.

 

즉 LinkedList 는 효율적이지못하다.

 

 

 

DeQue를 활용하자

 

Deque란?   Que랑 Stack의 특징을 다 가져온 리스트라고 보면 편하다.

 

Deque는 선입 후입 선출 후출 모두 O(1)으로 지원한다.

 

Deque의 메소드는 아래 링크에 정리해놨다.

 

https://taehoung0102.tistory.com/77

자바 API : 큐(Queue) ,Deque사용법

 

 

이 Deque와 아이디어를 합치면 효율성을 지키며 문제가 풀린다.

 

문제풀이

import java.util.*;
class Solution {
    
Deque<Integer> side1;
Deque<Integer> side2;
Deque<Deque<Integer>> inside;
    public int[][] solution(int[][] rc, String[] operations) {
      
        //첫번째기둥
        side1 = new LinkedList<>();
        //두번째기둥
        side2 = new LinkedList<>();
        //가운데 원소들
        inside = new LinkedList<>();
        
        
        int x = rc[0].length;
        int y = rc.length;
        
        // 맵 분리하기
        for(int i=0;i<y;i++){
            inside.addLast(new LinkedList<>());
            for(int j=0;j<x;j++){
                if(j==0){
                    side1.add(rc[i][j]);
                }
                else if(j==x-1){
                    side2.add(rc[i][j]);
                }
                else{                
                    inside.peekLast().addLast(rc[i][j]);
                }  
            }
        }
        
        // Operation 실시
        for(String o : operations){
            if(o.equals("Rotate")){
                rotate();
            }
            else{
                shift();
            }
        }
        
        int[][] answer = new int[y][x];
     
        
    
        for(int i=0;i<y;i++){
            
            int j=0;
            answer[i][j++]=side1.pollFirst();
            
            for(int e : inside.pollFirst()){
                answer[i][j++]=e;
            }
            
            answer[i][j]=side2.pollFirst();
        }
        
        return answer;
    }
    
    // Shift연산
    public void shift(){
        
       side1.addFirst(side1.removeLast());
       side2.addFirst(side2.removeLast());
       inside.addFirst(inside.removeLast());
    }
    // 회전연산
    public void rotate(){
                
        inside.peekFirst().addFirst(side1.removeFirst());
        side2.addFirst(inside.peekFirst().removeLast());
        inside.peekLast().addLast(side2.removeLast());
        side1.addLast(inside.peekLast().removeFirst());
        
    }
}