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

2022 KAKAO TECH INTERNSHIP

2차원 배열이 주어지고 Rotate와 ShiftRow를 동작한 결과값을 출력하는 문제입니다.

입력을 보았을 때 2차원 배열로 처리하면 시간초과가 발생하는 것을 알 수 있습니다.
덱을 사용해서 문제를 풀어보았습니다.

먼저 ShiftRow에 대해서 접근해보았습니다.
4*4 2차원 배열이 있을 때 아래와 같이 큐에 담습니다.

1 2 3 4
5 6 7 8
9 a b c
d e f g

=> 큐에 담음
q(
  q(1, 2, 3, 4)
  q(5, 6, 7, 8)
  q(9, a, b, c)
  q(d, e, f, g)
)

ShiftRow를 할 때 마다 큐를 하나 빼고 넣어줍니다.
q(
  q(1, 2, 3, 4)
  q(5, 6, 7, 8)
  q(9, a, b, c)
  q(d, e, f, g)
)

=> 뺀 값을 그대로 다시 삽입
q(
  q(d, e, f, g)
  q(1, 2, 3, 4)
  q(5, 6, 7, 8)
  q(9, a, b, c)
)

위와 같은 방식으로 ShiftRow를 처리 할 수 있었습니다.

Rotate에 접근해보겠습니다.
1 2 3 4
5 6 7 8
9 a b c
d e f g

=> 로테이트
5 1 2 3
9 6 7 4
d a b 8
e f g c

결과를 보면 가운데 값들은 움직이지 않고 테두리 쪽 값들만 Shift되는것을 알 수 있습니다.
덱을 사용해서 접근해보았습니다.

deque(1, 5, 9, d)  // 왼쪽
deque(4, 8, c, g)  // 오른쪽
deque(2, 3) //위
deque(e, f) //아래

Rotate가 실행 될 때 shift를 시켜주고 각 끝 부분만 시계방향으로 넘겨주면 됩니다.
Queue로는 tail쪽 처리를 할 수 없으므로 Deque를 사용해주었습니다.

이제 Rotate와 ShiftRow를 같이 처리하기 위해서 다음과 같이 deque를 사용했습니다.
1 2 3 4
5 6 7 8
9 a b c
d e f g

deque(1, 5, 9, d)  // 왼쪽
deque(4, 8, c, g)  // 오른쪽
deque(
  deque(2, 3) //위
  deque(6, 7) //중간
  deque(a, b) //중간
  deque(e, f) //아래
)

위와 같이 만들었을 세개의 deque 모두 값을 뺐다가 넣기만 하면 ShiftRow를 처리 할 수 있습니다.
Rotate는 위에서 진행한 것처럼 Shift를 해주고 시계방향으로 값을 넘겨주면 됩니다.

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
		this.prev = null;
	}
}
class Deque {
	constructor() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
	pushFront(item) {
		const newNode = new Node(item);
		if (this.getSize() === 0) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			newNode.next = this.head;
			this.head.prev = newNode;
			this.head = newNode;
		}
		this.size += 1;
	}
	pushBack(item) {
		const newNode = new Node(item);
		if (this.getSize() === 0) {
			this.head = newNode;
			this.tail = newNode;
		} else {
			this.tail.next = newNode;
			newNode.prev = this.tail;
			this.tail = newNode;
		}
		this.size += 1;
	}
	popFront() {
		if (this.getSize() === 0) {
			return -1;
		} else if (this.getSize() === 1) {
			const popedItem = this.head.item;
			this.head = null;
			this.tail = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() === 2) {
			const popedItem = this.head.item;
			this.head = this.head.next;
			this.tail.prev = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() > 2) {
			const popedItem = this.head.item;
			this.head.next.prev = null;
			this.head = this.head.next;
			this.size -= 1;
			return popedItem;
		}
	}
	popBack() {
		if (this.getSize() === 0) {
			return -1;
		} else if (this.getSize() === 1) {
			const popedItem = this.tail.item;
			this.head = null;
			this.tail = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() === 2) {
			const popedItem = this.tail.item;
			this.tail = this.tail.prev;
			this.head.next = null;
			this.size -= 1;
			return popedItem;
		} else if (this.getSize() > 2) {
			const popedItem = this.tail.item;
			this.tail.prev.next = null;
			this.tail = this.tail.prev;
			this.size -= 1;
			return popedItem;
		}
	}
	getSize() {
		return this.size;
	}

	isEmpty() {
		return this.getSize() ? 0 : 1;
	}

	getFront() {
		return this.getSize() ? this.head.item : -1;
	}

	getBack() {
		return this.getSize() ? this.tail.item : -1
	}
}

function solution(rc, operations) {
    const mdq = new Deque();
    const ldq = new Deque();
    const rdq = new Deque();    
    let answer = [[]];
    for(let i=0; i<rc.length; ++i){
        const dq = new Deque();
        ldq.pushBack(rc[i][0]);
        for(let j=1; j<rc[0].length-1; ++j){
           dq.pushBack(rc[i][j]); 
        }
        rdq.pushBack(rc[i][rc[i].length-1]);
        mdq.pushBack(dq);
    }
    for(let i=0; i<operations.length; ++i){
        if(operations[i] === "ShiftRow"){
            mdq.pushFront(mdq.popBack());
            ldq.pushFront(ldq.popBack());
            rdq.pushFront(rdq.popBack());
        } else if(operations[i] === "Rotate"){
            let sf = mdq.popFront();
            let sb = mdq.popBack();
            sf.pushFront(ldq.popFront());
            sb.pushBack(rdq.popBack());
            ldq.pushBack(sb.popFront());
            rdq.pushFront(sf.popBack());
            mdq.pushFront(sf);
            mdq.pushBack(sb);
        }        
    }
    for(let i=0; i<rc.length; ++i){
        let arr = [];
        let temp = mdq.popFront();
        temp.pushFront(ldq.popFront());
        temp.pushBack(rdq.popFront());
        for(let j=0; j<rc[0].length; ++j){
            arr[j] = temp.popFront();
        }
        answer[i] = arr;
    }
    
    return answer;
}