글 읽기 - 9019문제 node로 풀면 계속 시간초과 납니다.

kgc0517 6년 전 0

BFS로 푸는데 자꾸 시간 초과 나길래 AC받은 다른 언어 코드를 그대로 javascript로 변경해도 시간초과가 납니다..

코드가 잘 못 된건가요 아니면 다른 문제인건가요?

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin', 'utf8').split('\n');
var idx = 0;
var testCase = parseInt(input[idx++]);
var func = [D, S, L, R];
var type = ['D', 'S', 'L', 'R'];
Array.prototype.fill = function(size, what) {
  if(what !== undefined)  while(size) this[--size] = what;
  else while(size) this[--size] = [];
}
for(var j = 0; j < testCase; j++){
  var AB = input[idx++].split(' ');
  var A = parseInt(AB[0]);
  var B = parseInt(AB[1]);
  var q = [];
  var prev = [];
  prev.fill(10000,-1);
  prev[A] = A;
  var op = [];
  q.push(A);

  while (prev[B] === -1) {
    var cur = q.shift();
    for(var i = 0; i < 4; i++){
      var next = func[i](cur);
      if(prev[next] === -1){
        prev[next] = cur
        op[next] = type[i];
        q.push(next);
      }
    }
  }
  var stack = [];
  var cur = B;
  while (prev[cur] !== cur) {
    stack.push(op[cur]);
    cur = prev[cur];
  }
  var ans = '';
  while (stack.length) {
    ans += stack.pop();
  }
  console.log(ans);
}


function L(n) {
  return Math.floor(n * 10 % 10000 + n / 1000);
}

function R(n) {
  return Math.floor(n * 1000 % 10000 + n / 10);
}

function D(n) {
  return n * 2 % 10000;
}

function S(n) {
  return (n + 9999) % 10000;
}

ho94949 6년 전 3

문제의 시간제한이 C++등을 제외한 다른 언어에 대해 넉넉하지는 않습니다. (T가 굉장히 큰것으로 추정됩니다.)

문제가 있는 부분은 fill method로 js array를 처음부터 채우게 되면 가변배열처럼 작동을 하게 되지만, 임의의 index부터 채우게 되면 Dictionary(python의 Dictionary, C++의 map ..)으로 작동을 하게 됩니다.

그래서 fill 로직을 다음과 같이 바꾸면 돌아가긴 하는데 10.2초가 걸리네요.

  var prev = [];
  for(var i=0; i<10000; ++i) prev[i] = -1;

kgc0517 6년 전 0

아.. 정말 또 하나의 지식을 얻어 가네요 감사합니다.

저는 언제쯤이면 그런 세세한 내용까지 터득할려나요..ㅜㅜ

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

문제

문제

출처

ICPC

9019문제 node로 풀면 계속 시간초과 납니다.

kgc0517 6년 전 0

ho94949 6년 전 3

kgc0517 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말