글 읽기 - (자바스크립트) 시간초과가 왜 발생할까요?

kruno10 2년 전 0

1406번 에디터 문제를 자바스크립트로 풀었는데 시간초과를 받았습니다.

어느부분에서 시간초과가 발생했는지 잘 모르겠네요ㅜㅡㅜ

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

let str = input();
const n = Number(input());
const commandArray = [];
let cursor = str.length;

const commandFunc = {
  L: () => {
    if (cursor > 0) cursor--;
  },
  D: () => {
    if (cursor < str.length) cursor++;
  },
  B: () => {
    if (cursor > 0) {
      str = str.slice(0, cursor - 1) + str.slice(cursor);
      cursor--;
    }
  },
  P: char => {
    str = str.slice(0, cursor) + char + str.slice(cursor);
    cursor++;
  },
};

[...Array(n)].forEach(() => {
  commandArray.push(input().split(' '));
});

commandArray.forEach(command => {
  commandFunc[command[0]](command[1]);
});

console.log(str);

bupjae 2년 전 2

44번째 줄 및 49번째 줄의 시간복잡도는 각각 O(n) 입니다.

이 프로그램 전체의 시간복잡도는 O(nm) 이며, 최대 크기의 데이터일 때 대략 3000억 회 연산이 필요합니다.

이 정도 규모의 연산을 주어진 시간 내에 하는 것은 거의 불가능합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(자바스크립트) 시간초과가 왜 발생할까요?

kruno10 2년 전 0

bupjae 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말