baekjoon. 수 정렬하기 2

 

풀이

수 정렬하기 1번 문제와 톳씨하나 틀리지않고 동일한 문제 처럼 보이지만 시간 복잡도가 n^2보다 작아야한다

즉, 합병 정렬, 퀵 정렬, 힙 정렬, 기수 정렬.. nlog(n)의 시간 복잡도를 갖는 정렬 방법으로 정렬을 구현해야 하는 것

구현

첫번째

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));
    input.shift();
    let answer = [];
    function sort(left, right) {
        const newArr = [];

    while (left.length){
        if(left[0] >right[0]){
            newArr.push(right.shift());
        } else {
            newArr.push(left.shift());
        }
    }
    while (right.length){
        newArr.push(right.shift());
    }
    while (left.length){
        newArr.push(left.shift());
    }
    return newArr;
}

function merge(arr) {
    if(arr.length === 1) return arr;

    const mid = Math.floor(arr.length/2);

    return sort(merge(arr.slice(0,mid)),merge(arr.slice(mid)));
}
answer = merge(input);
answer.forEach(v=>console.log(v));

그냥 내가 가지고 있는 지식으로 합병 정렬을 구현했는데 이번에 문제를 풀면서 수박 겉 핥기 식으로 흉내만 내고 있다는 것을 깨달았다

문제점

왜 합병 정렬인데 시간초과가 뜨지? 하며 여기저기 검색해 본 결과.. 몇가지 문제점을 알 수 있었다

• shift는 연산 속도가 매우 느리다
• console.log는 매우 느리다

shift

배열의 제일 처음에서 연산하는 shift,unshift의 경우 배열의 마지막 부분에서 추가하고 빼는 pop, push와는 다르게

연산을 하고 나면 배열 전체를 앞으로 한칸씩 당기거나 밀어야하기 때문에 연산속도는 O(n)이 된다

그렇기 때문에 나 편하자고 shift로 구현하면 합병 정렬의 이점을 볼 수가 없는 것

그래서 sort함수 내에서 left배열과 right배열을 받아서 정렬된 배열을 생성할 때는 번거롭더라도 인덱스를 이용해야한다

console.log

자바의 System.out.print를 쓰면 속도가 느려서 BufferedWriter를 쓰듯

노드의 console.log의 속도도 매우 느리다

그래서 정렬된 배열을 출력할 때는 join('\n')을 사용해서 줄바꿈을 넣어주고 한번에 출력하는 것이 빠르다

두번째

// const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));
let answer = [];

input.shift();
function sort(left, right) {
    let i=0,j=0,k=0;
    const newArr = Array(left.length+right.length);

    while (left.length>i&&right.length>j){
        if(left[i] >right[j]){
            newArr[k++] = right[j++];
        } else {
            newArr[k++] = left[i++];
        }
    }

    while (right.length>j){
        newArr[k++] = right[j++];
    }

    while (left.length>i){
        newArr[k++] = left[i++];
    }

    return newArr;
}

function merge(arr) {
    if(arr.length === 1) return arr;

    const mid = Math.floor(arr.length/2);

    return sort(merge(arr.slice(0,mid)),merge(arr.slice(mid)));
}
answer = merge(input);
console.log(answer.join('\n'));

검색하고 찾은 잘못된 점을 적용하기 위해 조건문을 여기저기 바꾸고 실행해보니 통과하였다