[백준] 5430_AC (Javascript)

문제

BOJ5430_AC

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let T = +input[0];
const totalAnswer = [];
let inputIdx = 1;

while (T--) {
    const p = input[inputIdx++];
    const n = +input[inputIdx++];
    const arr = JSON.parse(input[inputIdx++]);

    let answer = [];
    let front = 0;
    let rear = arr.length - 1;
    let error = false;
    let reversed = false;
    for (let i = 0; i < p.length; i++) {
        if (p[i] === 'R') {
            reversed = reversed ? false : true;
        } else {
            if (reversed) {
                if (arr[rear] === undefined) {
                    error = true;
                    break;
                } else rear--;
            } else {
                if (arr[front] === undefined) {
                    error = true;
                    break;
                } else front++;
            }
        }
    }
    if (error) {
        totalAnswer.push('error');
    } else {
        if (reversed) {
            for (let i = rear; i >= front; i--) answer.push(arr[i]);
        } else {
            for (let i = front; i <= rear; i++) answer.push(arr[i]);
        }
        totalAnswer.push(JSON.stringify(answer));
    }
}
console.log(totalAnswer.join('\n'));

시간 복잡도

이 문제는 자칫하면 시간초과나기 좋은 문제다.

우선 단순한 접근법부터 떠올려 보면, R이 등장할 때마다 reverse() 함수를 사용해서 배열을 뒤집고 D가 등장할 때마다 shift() 함수를 사용해서 배열에 앞에 있는 원소를 제거해주는 방법이 있다.
이 방법의 시간복잡도는 reverse 와 unshift 함수의 시간 복잡도가 $O(N)$ 이고, 이걸 p번 반복한다.
$p\le100,000$, $n\le100,000$ 이니, 10$^1$$^0$라서 시간초과가 발생한다. 게다가 추가로 테스트케이스가 최대 100개이니 10$^1$$^2$번 연산을 수행하기 때문에 무조건 시간초과가 날 수밖에 없다.

그렇다면 직접 큐를 구현해주는 방법은 어떨까?
큐를 사용하면 맨 앞에 있는 원소를 $O(1)$의 시간복잡도로 제거할 수 있으므로 unshift()함수를 사용하지 않아도 된다. 하지만 이제 배열을 뒤집는 것이 문제다.

배열을 뒤집으려면 결국엔 $O(N)$의 시간이 걸리기 때문에 배열에 데이터가 100,000개가 있고, p의 길이가 100,000에다가 원소는 모두 R로 꽉 차있을 경우만 해도 시간초과가 난다.

이제 그 해결책을 알아보자.

풀이

이렇게 문제를 풀다보면 의문점을 하나 가질 수 있다.

"배열을 굳이 매번 뒤집어줄 필요가 있을까?"

배열을 뒤에서부터 읽으면 배열을 뒤집었을 때와 동일한 효과를 낼 수 있다.

더 자세히 설명해보자면, 우선 front 와 rear 라는 변수를 만들어주고 각각 배열의 시작 인덱스와 마지막 인덱스를 가리키도록 해준다. 그리고 reversed 라는 스위치 변수를 만들어서 만약 R이 등장할 경우 이 변수를 true 와 false로 변경해주면서 현재 배열이 뒤집힌 상태인지 아닌지를 알 수 있도록 해주고, 배열이 뒤집힌 상태에서 D가 나왔다면 rear를 1 감소시켜주고, 뒤집히지 않은 상태에서 D가 나왔다면 front를 1 증가시켜준다.

이렇게 인덱싱을 통해서 코드를 짠다면 시간 초과에서 벗어날 수 있다.

코드 (정리)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');

let T = +input[0];
const totalAnswer = [];
let inputIdx = 1;

while (T--) {
    const p = input[inputIdx++];
    const n = +input[inputIdx++];
    const arr = JSON.parse(input[inputIdx++]);

    let front = 0;
    let rear = arr.length - 1;
    let error = false;
    let reversed = false;

    for (let i = 0; i < p.length; i++) {
        if (p[i] === 'R') reversed = !reversed;
        else {
            if (front > rear) {
                error = true;
                break;
            }
            if (reversed) rear--;
            else front++;
        }
    }
    if (error) {
        totalAnswer.push('error');
    } else {
        let answer = arr.slice(front, rear + 1);
        answer = reversed ? answer.reverse() : answer;
        totalAnswer.push(JSON.stringify(answer));
    }
}
console.log(totalAnswer.join('\n'));