[알고리즘-JS] Special Sort (구글 인터뷰)

문제

N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다. 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다.

또한 양의정수와 음의 정수의 순서에는 변함이 없어야 한다.

 

입력 예제

8

1 2 3 -3 -2 5 6 -6

 

출력 예제

-3 -2 -6 1 2 3 5 6

 

 

 

 

풀이

일반 오름차순 정렬로 하면 음수, 양수 각각의 순서도 정렬되기 때문에 버블 정렬로 해결해야 한다.

 

function solution(arr) {
  let answer = arr; // 얕은 복사
  
  // 버블 정렬
  for (let i = 0; i < arr.length-1; i++) {
    // 맨 뒤 요소는 계속 확정이므로 확인 X
    for (let j = 0; j < arr.length-1-i; j++) {
      // j가 양수고, j 뒤 요소가 음수인 경우 자리 바꿈
      if (arr[j] > 0 && arr[j+1] < 0) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  
  return answer;
}