[Silver V] 수 정렬하기 2 - 2751 (JavaScript)

문제 링크

 

 

분류

정렬

 

문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

코드

 

1. sort()

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

let n = Number(input[0]);
let arr = [];
for (let i = 1; i <= n; i++) {
  arr.push(Number(input[i]));
}

arr.sort((a, b) => a - b) // 오름차순 정렬

// 정렬된 결과를 출력
let answer = "";
for (let i = 0; i < arr.length; i++) {
  answer += arr[i] + '\n';
}

console.log(answer);

 

2. 병합 정렬

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

let n = Number(input[0]);
let arr = [];
for (let i = 1; i <= n; i++) {
  arr.push(Number(input[i]));
}


// 병합 정렬 수행
function merge(arr, left, mid, right) {
  let i = left;
  let j = mid + 1;
  let k = left;

  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
    else sorted[k++] = arr[j++];
  }
  
  // 왼쪽 배열에 대한 처리가 다 끝난 경우
  if (i > mid) {
    for (; j <= right; j++) sorted[k++] = arr[j];
  }
  
  // 오른쪽 배열에 대한 처리가 다 끝난 경우
  else {
    for (; i <= mid; i++) sorted[k++] = arr[i];
  }
  
  // 정렬된 배열 결과를 원본 배열에 반영하기
  for (let x = left; x <= right; x++) {
    arr[x] = sorted[x];
  }
}


// 병합 정렬
function mergeSort(arr, left, right) {
  if (left < right) {
    let mid = parseInt((left + right) / 2); // 2개의 부분 배열로 분할
    mergeSort(arr, left, mid); // 왼쪽 부분 배열 정렬
    mergeSort(arr, mid + 1, right); // 오른쪽 부분 배열 정렬
    merge(arr, left, mid, right); // 정렬된 2개의 배열을 하나로 병합
  }
}


let sorted = Array.from({ length: arr.length }, () => 0); // 임시 정렬 배열 정의
mergeSort(arr, 0, arr.length - 1);

// 정렬된 결과를 출력
let answer = "";
for (let i = 0; i < arr.length; i++) {
  answer += arr[i] + '\n';
}

console.log(answer);

 

• JavaScript에서 제공하는 sort()는 시간 복잡도 O(NlogN)을 보장한다.
• 따라서, 본 문제에서는 N의 최대 크기가 100만이라는 점에서 sort()와 병합정렬로 해결할 수 있다.
• 시간 복잡도 O(N^2)의 정렬 알고리즘으로는 시간 초과를 받는다.