글 읽기 - [node.js] [연결리스트 구현] 시간초과 오류 봐주시면 감사하겠습니다..

dannykim 3년 전 0

Node.Js로 연결리스트를 구현하여 문제를 풀어보았습니다.

예제 3개는 문제없이 통과되고 제가 생각했던 모든 건 다 잘 작동하는 것 같습니다.

다만 0.3초의 벽이 높았던 것인지.. 시간초과로 인해 통과를 못하고 있습니다.

제출한 사람들 중에 node.js로 통과하신 분도 있으신걸 보아

언어의 문제는 아닌거 같고..

혹시 제가 놓친 부분이 있는지 봐주시면 감사하겠습니다.

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const text = input[0].split("");
const N = parseInt(input[1]);
// console.log(text, N);

const MX = 100000 + 5;
const dat = new Array(MX).fill(0);
const pre = new Array(MX).fill(-1);
const nxt = new Array(MX).fill(-1);
let unused = 1;

let cur = 0;
for (let i = 0; i < text.length; i++) {
	insert(cur, text[i]);
	cur++;
}

// console.log(dat.slice(0, text.length + 1));
// console.log(pre.slice(0, text.length + 1));
// console.log(nxt.slice(0, text.length + 1));

for (let i = 0; i < N; i++) {
	let line = input[i + 2].split(" ");
	let operator = line[0];
	let operand = line[1];
	// console.log("operator operand", operator, operand);

	switch (operator) {
		case "L":
			if (pre[cur] !== -1) cur = pre[cur];
			break;
		case "D":
			if (nxt[cur] !== -1) cur = nxt[cur];
			break;
		case "B":
			if (pre[cur] !== -1) {
				erase(cur);
				cur = pre[cur];
			}
			break;
		case "P":
			insert(cur, operand);
			cur = nxt[cur];
			break;
	}
	// traverse();
}

traverse();

function traverse() {
	// process.stdout.write(cur + " ");
	for (let i = nxt[0]; i !== -1; i = nxt[i]) {
		process.stdout.write(dat[i]);
	}
	console.log("");
}

function erase(addr) {
	//앞의 원소
	nxt[pre[addr]] = nxt[addr];
	//뒤의 원소
	if (nxt[addr] !== -1) {
		pre[nxt[addr]] = pre[addr];
	}
}

function insert(addr, val) {
	//새로운 원소 생성
	dat[unused] = val;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];

	//뒤의 원소와 연결
	if (nxt[addr] !== -1) {
		pre[nxt[addr]] = unused;
	}
	//앞의 원소와 연결
	nxt[addr] = unused;

	unused++;
}

dannykim 3년 전 1

해결하였습니다.

자문자답입니다만, traverse 에서 출력시 매번 process.stdout.write(dat[i]);를 호출하지 않고

answer += dat[i]; 로 answer에 넣어둔 다음에

마지막에 한번에 출력하니 되네요

문제는 출력처리였습니다...

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

문제

문제

출처

ICPC

[node.js] [연결리스트 구현] 시간초과 오류 봐주시면 감사하겠습니다..

dannykim 3년 전 0

dannykim 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말