[ 자바스크립트(JavaScript) ] section07 - 3 - Special Sort(구글 인터뷰)

📍 section07 - 3 - Special Sort(구글 인터뷰)

문제: 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다. 이때, 양의 정수와 음의 정수의 순서는 변함이 없어야 한다. GeeksforGeeks에서 관련 문제를 가져왔다. 영어로 풀고 싶으면 사이트에 들어가서 푸는것을 권장한다. 이 문제를 풀때 2가지 방법이 떠올랐다.

 

1. 한 개는 for문을 돌면서 음수 먼저 answer에 push하고 또 for문을 돌면서 양수를 answer에 push 하는 방법
2. 버블 정렬 방식의 일부를 가져와서 j가 음수이고 j+1이 양수면 swap하는 방법

 

시간 복잡도는 1번(O(N))으로 더 빠르지만 만약, 코딩 인터뷰를 할 때 정렬을 이용해서 풀어보라고 할 때는 2번(O(N^2))을 이용하면 된다.

 

728x90

 

// 1번 방법
let n = 8;
let arr = [1, 2, 3, -3, -2, 5, 6, -6];

console.log(solution(n, arr));
👉🏽 [ -3, -2, -6, 1, 2, 3, 5, 6 ]

function solution(n, arr){
    let answer = [];

    for (let x of arr){
        if (x<0) answer.push(x);
    }

    for (let x of arr){
        if (x>0) answer.push(x);
    }
    return answer
}

 

// 2번 방법
let n = 8;
let arr = [1, 2, 3, -3, -2, 5, 6, -6];

console.log(solution(n, arr));
👉🏽 [ -3, -2, -6, 1, 2, 3, 5, 6 ]

function solution(n, arr){
    for (let i=0; i<n-1; i++){
        for (let j=0; j<n-i-1; j++){
            if (arr[j]>0 && arr[j+1]<0) [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        }
    }
    return arr;
}