백준 / 구현 / 5430번 / AC / JS

문제 간단설명

숫자 배열이 주어진다. 명령어는 R과 D가 주어지는데 R은 배열 뒤집기, D는 배열의 맨 앞에서 하나를 제거하는 것이다.

 

제한 사항

• T <= 100
• 1 <= p.length <= 100,000
• 0 <= n <= 100,000
• 1 <= 배열의 각 정수 <= 100
• p.length + n <= 700,000

 

실패 코드 (메모리 초과)

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

const T = +input.shift();

function solution() {
  const result = [];

  for (let testCase = 1; testCase <= T; testCase++) {
    const p = input.shift();
    const n = +input.shift();

    let numberList = input.shift().match(/\d+/g) || [];
    numberList = numberList.map(Number);

    for (const command of p) {
      if (command === 'R') {
        numberList = reverse(numberList);
      } else if (command === 'D') {
        numberList = deleteFirstNumber(numberList);

        if (numberList === 'error') {
          break;
        }
      }
    }

    result.push(numberList);
  }

  console.log(
    result.map((el) => (el !== 'error' ? JSON.stringify(el) : el)).join('\n')
  );
}

function reverse(numberList) {
  return [...numberList].reverse();
}

function deleteFirstNumber(numberList) {
  if (numberList.length === 0) {
    return 'error';
  }

  const [_, ...newArray] = numberList;

  return newArray;
}

solution();

 

로직은 크게 문제가 없었다.

 

하지만 메모리 초과가 나온 이유는, reverse()와 deleteFirstNumber() 함수 구현에 있었다.

원본 배열을 수정하지 않기 위해 인자로 받고 전개 연산자로 깊은 복사를 통해 새로운 배열을 만들어주고, 그 배열을 조작해서 반환해주었다.

 

따라서, 수많은 배열을 계속해서 만들면서 메모리 초과가 발생했다.

 

실패 코드 (시간 초과)

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

let index = 0;
const T = +input[index++];

function solution() {
  const result = [];

  for (let testCase = 1; testCase <= T; testCase++) {
    const p = input[index++];
    const n = +input[index++];

    let numberList = JSON.parse(input[index++]).map(Number);

    for (const command of p) {
      if (command === 'R') {
        numberList.reverse();
      } else if (command === 'D') {
        if (numberList.length === 0) {
          numberList = 'error';
          break;
        }
        numberList = numberList.slice(1);
      }
    }

    result.push(numberList);
  }

  console.log(
    result.map((el) => (el !== 'error' ? JSON.stringify(el) : el)).join('\n')
  );
}

solution();

 

처음에는 시간 초과가 shift() 메소드 때문에 나는 줄 알았다.

그래서 input의 각 값을 shift()를 통해 얻어오는 대신, 인덱스 변수를 두고 참조하게 하였다.

하지만 그래도 시간 초과가 났다.

 

물론 위에서 생각한 input의 값을 가져오는 부분에서의 shift() 연산의 영향이 아예 없지는 않겠지만, 결정적 문제는 다른 곳에 있었다.

 

성공 코드

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

let index = 0;
const T = +input[index++];

function solution() {
  const result = [];

  for (let testCase = 1; testCase <= T; testCase++) {
    const p = input[index++];
    const n = +input[index++];

    let numberList = JSON.parse(input[index++]).map(Number);

    let isReversed = false;
    let isError = false;

    for (const command of p) {
      if (command === 'R') {
        isReversed = !isReversed;
      } else if (command === 'D') {
        if (numberList.length === 0) {
          isError = true;
          break;
        }

        // 만약 뒤집힌 상태라면, 뒤집지 않고 뒤에서 하나 제거한다.
        if (isReversed) {
          numberList.pop();
        } else {
          // 뒤집힌 상태가 아니라면 앞에서 하나 제거한다.
          numberList.shift();
        }
      }
    }

    // 뒤집힌 상태이고, 에러가 나지 않았다면 뒤집어준다.
    if (isReversed && !isError) {
      numberList.reverse();
    }
    if (isError) {
      result.push('error');
    } else {
      result.push(numberList);
    }
  }

  // 배열을 그대로 출력하게 되면 양쪽 괄호([])가 보이지 않기 때문에 객체 자체를 문자열로 바꿔준다.
  console.log(
    result.map((el) => (el !== 'error' ? JSON.stringify(el) : el)).join('\n')
  );
}

solution();

 

아무래도 확실한 것은 수많은 shift()와 reverse()의 사용이 분명했다.

 

shift()는 O(n)의 시간 복잡도를 가진다.

reverse() 또한 O(n)의 시간 복잡도를 가진다.

 

모든 명령마다 이 두 메소드를 호출하기 때문에 시간 복잡도가 커졌던 것이다.

 

따라서 이 배열을 뒤집어야 하는지, 에러가 발생하는지에 대한 플래그 변수인 isReversed와 isError 변수를 두었다.

'R' 명령이 들어왔다고 해서 바로 뒤집지 말고, 뒤집어야 하는지 일단 변수를 조작한다. isReversed를 true로 만들면 된다.

그리고 나서 'D' 명령이 이어서 들어온다면 앞에서 shift() 하는 것이 아닌, 뒤에서 pop()을 한다.

pop()은 시간 복잡도가 O(1)이기 때문이다.

그리고 마지막에 isReversed의 true 여부에 따라 뒤집기를 딱 한 번만 수행하면 된다.

 

각 명령마다 reverse()나 shift()를 했던 것과 달리 확실히 시간 복잡도를 줄여서 통과할 수 있었다.