글 읽기 - 퀵소트 잘못짠게 있을까요?

kkw564 1년 전 0

단순 퀵정렬 문제인데

노드로 풀때 sort없이 풀려하는데 40%에서 timeout이 나네요

어디가 문제였을까요 ??

const { reverse } = require("dns");
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const len = input[0];
  const arr = input.slice(1).map((value) => parseInt(value));

  qsort(arr, 0, len - 1);
  arr.reverse();

  // const len = input[0];
  // const arr = [];

  // for (let i = 1; i < input.length; i++) arr.push(+input[i]);
  // arr.sort((a, b) => b - a);

  let ans = "";
  for (let value of arr) {
    ans += value + "\n";
  }
  console.log(ans);
});

function qsort(arr, start, end) {
  let pivot = arr[start];

  let left = start;
  let right = end;
  while (left <= right) {
    if (left >= right) {
      return;
    }
    while (arr[right] >= pivot && right > left) {
      right--;
    }
    if (right > start) {
      arr[left] = arr[right];
    }
    while (arr[left] <= pivot && left < right) {
      left++;
    }
    if (left < end) {
      arr[right] = arr[left];
    }

    if (left == right) {
      arr[left] = pivot;
      qsort(arr, start, right - 1);
      qsort(arr, left + 1, end);
    }
  }
}

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

문제

문제

출처

ICPC

퀵소트 잘못짠게 있을까요?

kkw564 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말