(javascript) 행렬과 연산

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

프로그래머스

은근히 어려운 문제였다.

핵심 아이디어를 떠올리지 못하면 효율성 테스트를 통과하지 못할 것 같다.

 

 정확도 테스트만 있었다면 단순하게 모든 원소를 일일이 이동하도록 구현해도 통과할 수 있었을 것이다.

 그러나 효율성 테스트를 통과하려면 그래서는 안된다.

 

 핵심 아이디어는 회전 명령을 수행하기 위해 행렬의 테두리만을 따로 관리하는 것이다.

 

 행렬의 제일 왼쪽 열, 제일 오른쪽 열, 제일 윗 행, 제일 아랫 행을 각각 큐로 관리하면 회전 연산을 O(1)만에 처리할 수 있다는 아이디어다.

 나는 아무리해도 효율성 테스트를 통과할만한 아이디어가 떠오르지 않아서 인터넷에 검색해봤다.

 

 자바스크립트에서는 배열에 직접 push, pop, shift, unshift 연산을 수행할 수 있지만, 내부적으로는 모든 원소의 위치를 하나씩 밀고 당기기 때문에 O(n)의 시간복잡도를 가진다. 따라서 이 문제에서 사용하기 위한 커스텀 큐를 구현해야했다.

 직접 구현한 큐는 내부에 배열을 가지고, 큐의 시작 인덱스, 끝 인덱스를 따로 가리키는 방법으로 구현했다. 배열의 원소 전체를 옮기기 보다 가리키는 위치만 옮기는 방법으로 O(1)만에 모든 연산을 처리할 수 있다.

 

 마지막으로 한가지 함정같은 케이스가 있었는데, 행렬의 열의 갯수가 2개인 경우이다.

 내가 구현한 방법으로는 열이 2개인 경우, 즉 body가 없는 경우 예외 처리를 해주어야 했다. 이 부분을 놓쳐서 효율성 테스트 하나를 실패했다.

 

코드

function solution(rc, operations) {
    const col = rc.length;
    const row = rc[0].length;
    var answer = Array.from({ length: col }, () => new Array(row));

    var head = new Queue(col);
    var tail = new Queue(col);
    var body = new Array(col);
    for (var i = 0; i < col; i++) {
        head.push(rc[i][0]);
        tail.push(rc[i][row - 1]);
    }
    for (var i = 0; i < col; i++) {
        var q = new Queue(row - 2);
        for (var j = 1; j < row - 1; j++) {
            q.push(rc[i][j]);
        }
        body[i] = q;
    }

    let top = 0;
    let bot = col - 1;
    for (var i = 0; i < operations.length; i++) {
        if (operations[i] === 'ShiftRow') {
            // 평행이동
            head.translate();
            tail.translate();
            top--;
            bot--;
            if (top < 0) top += col;
            if (bot < 0) bot += col;
        } else if (operations[i] === 'Rotate') {
            // 회전
            if (row == 2) {
                var temp = head.unshift();
                head.push(tail.pop());
                tail.shift(temp);
            } else {
                var temp = head.unshift();
                head.push(body[bot].unshift());
                body[bot].push(tail.pop());
                tail.shift(body[top].pop());
                body[top].shift(temp);
            }
        }
    }

    for (var i = 0; i < col; i++) {
        answer[i][0] = head.unshift();
        answer[i][row - 1] = tail.unshift();
        for (var j = 1; j < row - 1; j++) {
            var t = i + top;
            if (t >= col) t -= col;
            answer[i][j] = body[t].unshift();
        }
    }
    return answer;
}

class Queue {
    constructor(size) {
        this.size = size;
        this.array = new Array(size);
        this.head = 0;
        this.tail = -1;
    }

    // 앞에서 추가
    shift(value) {
        this.head--;
        if (this.head < 0)
            this.head += this.size;
        this.array[this.head] = value;
    }

    // 앞에서 제거
    unshift() {
        let result = this.array[this.head];
        this.head++;
        if (this.head >= this.size)
            this.head -= this.size;
        return result;
    }

    // 뒤에 추가
    push(value) {
        this.tail++;
        if (this.tail >= this.size)
            this.tail -= this.size;
        this.array[this.tail] = value;
    }

    // 뒤에서 제거
    pop() {
        let result = this.array[this.tail];
        this.tail--;
        if (this.tail < 0) this.tail += this.size;
        return result;
    }

    translate() {
        this.head--;
        this.tail--;
        if (this.head < 0) this.head += this.size;
        if (this.tail < 0) this.tail += this.size;
    }

    toArray() {
        let result = new Array(this.size);
        for (var i = 0; i < this.size; i++) {
            result[i] = this.array[this.head];
            this.head++;
            if (this.head >= this.size) this.head -= this.size;
        }
        return result;
    }
}