알고리즘 :: 백준 2751번 - 수 정렬하기 #JavaScript

알고리즘 공부하며 배운내용

 

 

백준 2751번 - 수 정렬하기

오름차순으로 정렬한다.

 

 

들어오는 값

첫 줄에 전체 숫자 개수 N, 둘째 줄부터 N개의 숫자

중복된 숫자는 안들어온다.

예)

5

5

4

3

2

1

 

 

구하고 싶은 값

오름차순 정렬

예)

1

2

3

4

5

 

 

생각

병합정렬로 풀어보자

 

 

코드

 

첫 번째 코드 - 메모리 초과

병합 정렬 방법

병합 정렬 코드가 메모리 초과로 안된다

다른 정렬로 해야겠다

 

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

let [N, ...order] = input.map(Number)
order = mergeSort(order)
function mergeSort(arr) {
    if(arr.length < 2) {
        return arr
    }

    let mid = Math.floor(arr.length / 2)
    let left = arr.slice(0, mid)
    let right = arr.slice(mid)

    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    let result = []

    let l_index = 0
    let r_index = 0

    while (l_index < left.length && r_index < right.length){
        if(left[l_index] < right[r_index]){
            result.push(left[l_index])
            l_index++
        }
        else {
            result.push(right[r_index])
            r_index++
        }
    }
    return [...result, ...left.slice(l_index), ...right.slice(r_index)]
}

console.log(order.join('\n'))

 

 

두 번째 코드 - 런타임 에러 (ENOENT)

간단히 sort로 한 정렬

런 타임 에러, node.js에 fs를 사용할 경우 런타임에러가 나온다고 한다.

const fs = require('fs')
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n')

let [N, ...order] = input.map(Number)

order = order.sort((a, b) => (a - b))
console.log(order.join('\n'));

 

세 번째 코드 - 통과

fs 대신 readline으로 사용한 코드

fs가 사용에 편리하지만 백준 이용시 이 방법에 익숙해져야 되나보다

let input = []

require('readline')
    .createInterface(process.stdin, process.stdout)
    .on('line', function(x) {
        input.push(x.trim())
    })
    .on('close', function() {
        const [N, ...order] = input.map(Number)
        const result = order.sort((a, b) => a - b)
        console.log(result.join('\n'));
    })