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

kruno10 2년 전 0

어느 부분에서 시간초과가 발생하는걸까요!? 😂

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

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

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

const str = input();
const t = Number(input());
const commandArray = [];
let cursor = str.length;
const res = str.split('');

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

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

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

console.log(res.join(''));

bupjae 2년 전 3

37번째 줄과 42번째 줄의 시간복잡도는 여전히 각각 O(n) 입니다.

배열의 임의의 위치에 원소를 삽입하거나 삭제하려는 시도는 O(n) 입니다.

이 문제를 제한된 시간에 풀기 위해서는 다음 중 한 가지 방법을 선택해야 합니다.

1) 배열의 맨 끝에서만 삽입 또는 삭제 연산을 수행하도록 설계하기

2) 임의의 위치에 원소를 삽입하거나 삭제하는 연산을 O(1) 에 수행할 수 있는 자료구조 사용하기

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

문제

문제

출처

ICPC

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

kruno10 2년 전 0

bupjae 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말