[JS] 행렬과 연산

Deque를 활용하여 해결하였다.

 

 

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

프로그래머스

 

 

문제 자체는 단순했다. 행렬을 밑으로 밀어내거나 시계방향으로 회전하는 기능을 구현하면 되었다.

단, 시간복잡도를 생각해야 하는 문제이다.

 

행렬을 밑으로 밀어내는 것 자체는 어렵지 않다. Deque로 쉽게 구현할 수 있다. 

시계방향으로 회전하는 기능또한 Deque로 구현할 수 있다.

 

이 두가지를 동시에 할 수 있게 하기 위해 Deque를 아래와 같이 조금은 특이하게 구조를 잡아보았다.

 

파란색으로 되어 있는 부분을 Deque라고 생각하였다.

즉 왼쪽,오른쪽 열을 Deque로 두고 가운데 부분을 2중 Deque를 사용하였다.

 

이 경우 회전이나 아래로 미는 것 모두 행렬의 한 행이나 열을 모두 탐색할 필요도 없기에 시간초과를 할 수 있다!

 

좀 어려운 점은 JS는 Deque가 지원을 안해줘서 만들어서 구현해야 하기에 귀찮았다.

 

 

 

 

 

 

class Node{
    constructor(val){
        this.val = val
        this.prev = null
        this.next = null
    }
}

//Deque 구현
class Deque{
    constructor(){
        this.head = null
        this.tail = null
        this.size = 0
    }
    
    push(node){
        this.size ++
        if(this.head===null){
            this.head = node
            this.tail = node
            return
        }
        this.tail.next = node
        node.prev = this.tail
        this.tail = node
        
    }
    
    pushLeft(node){
        this.size ++
        if(this.head===null){
            this.head = node
            this.tail = node
            return
        }
        this.head.prev = node
        node.next = this.head
        this.head = node
    }
    
    pop(){
        const ret = this.tail
        if(this.size===0) return
        if(this.size===1){
            this.head = null
            this.tail = null
            this.size = 0
            return ret
        }
        this.tail.prev.next = null
        this.tail = this.tail.prev
        this.size--
        return ret
    }
    
    popLeft(){
        const ret = this.head
        if(this.size===0) return
        if(this.size===1){
            this.head = null
            this.tail = null
            this.size = 0
            return ret
        }
        
        this.head.next.prev = null
        this.head = this.head.next
        this.size --
        return ret
    }
}



function solution(rc, operations) {
    
    const leftCol = new Deque()
    const rightCol = new Deque()
    const center = new Deque()
    
    //Deque로 변환
    for (const ary of rc){
        leftCol.push(new Node(ary[0]))
        rightCol.push(new Node(ary[ary.length-1]))
        const centerNode = new Deque()
        for (const arr of ary.slice(1,ary.length-1)){
            centerNode.push(new Node(arr))
        }
        center.push(new Node(centerNode))
    }
    
    const shiftRow = () => {
        leftCol.pushLeft(leftCol.pop())
        rightCol.pushLeft(rightCol.pop())
        center.pushLeft(center.pop())
    }
    
    const rotate = () => {
        center.head.val.pushLeft(leftCol.popLeft())
        rightCol.pushLeft(center.head.val.pop())
        center.tail.val.push(rightCol.pop())
        leftCol.push(center.tail.val.popLeft())
    }
    
    
    for (const operation of operations){
        if (operation === "Rotate") rotate()
        else shiftRow()
    }
    
    //Deque -> Array 변환
    const ret = []
    for (let i = 0 ; i < rc.length ; i++){
        const tmp = []
        tmp.push(leftCol.popLeft().val)
        const nums = center.popLeft().val
        while(nums.head){
            tmp.push(nums.popLeft().val)
        }
        tmp.push(rightCol.popLeft().val)
        ret.push(tmp)
    }
    
    return ret
    
}