Sort the odd<6 kyu>

jjanmo·2020년 1월 1일

문제

You have an array of numbers.
Your task is to sort ascending odd numbers but even numbers must be on their places.
Zero isn't an odd number and you don't need to move it. If you have an empty array, you need to return it.

Example

sortArray([5, 3, 2, 8, 1, 4]) == [1, 3, 2, 8, 5, 4])

🚩 문제 해석
주어진 배열을 정렬하시오. 단, 짝수는 옮기지 말고 홀수인 경우만 정렬하시오.

문제 접근

문제는 굉장히 간단했다. 간단한 문제를 어떻게 간단하게 풀 것인지는 또 다른 문제이긴했다. 가장 단순하게(?) 생각하면 이중 for문을 돌려서 홀수일 때만 그 값을 선택해서 비교하여 교환해주는 방식으로 풀면 될거라고 생각했다. 실제로 그렇게 풀이를 하였다.
이 방식말고도 filter()를 활용하려고 하였는데, 한 부분에서 막혀서 그 풀이는 버렸는데, 역시 어떤 CLEVER 한 외국 친구가 성공한 비슷한 방식의 풀이를 보게되었다.

문제 풀이

나의 풀이

function sortArray(array) {
   for(let i = 0; i < array.length; i++){
    if(array[i] % 2 === 0 )  continue;
    else {
      for(let j = i; j < array.length; j++){
        if(array[j] % 2 !== 0 && array[i] > array[j]){
          const tmp = array[i];
          array[i] = array[j];
          array[j] = tmp;
        }
      }
    }//else
  }//for i
  return array;
}

위에서 말한 것처럼 짝수일 때는 건너뛰고 홀수일 때만 순회하면서 정렬하였다. 그런데 지금까지 난 이게 선택정렬이라고 생각하고 사용했다. 이번에 문제를 풀면서 다시 찾아보니 지금 써져있는 것이 선택정렬은 맞는데, 좀 더 비효율적인 선택정렬임을 알게 되었다. 기존 선택정렬은 선택된 값의 뒷 쪽에서 최소값을 찾아서 그것과 교환을 한다. 그런데 내가 사용한 것은 뒷 쪽의 요소들을 모두 비교하고 작은 값이 나오면 모두 교환하게 된다. 최악의 경우 배열의 길이 100이라면 99번 교환을 반복하게 될 수도 있다. 교환 과정에 있어서 비효율이 나타나는 것이다. 이제까지 이렇게 사용했는데, 이제라도 알게 된 것을 다행이라고 생각한다. 가장 기본적인 정렬 알고리즘 에 대해서 다시 정리를 해야할 필요성이 생겼다.

Best Solution

1  function sortArray(array) {
2    const odd = array.filter((x) => x % 2).sort((a,b) => a - b);
3    return array.map((x) => x % 2 ? odd.shift() : x);
4  }

이 풀이 밑에 달린 댓글들을 보면 효율성에 대해서 말이 많았다. 하지만 효율을 논하기에는
이 문제가 많이 단순하지 않나 라는 생각을 해본다. 그래서 우선 이 코드가 어떻게 동작하고 있는지에 초점을 맞춰서 생각해보겠다.

처음에 filter()를 사용한다고 했을 때, 2번라인의 코드까지는 생각을 했다. 그런데 문제가 생겼다. 그것은 어떻게 짝수를 원래 인덱스값을 주고 그 자리에 넣어주는냐 였다.

  function sortArray(array) {
    const evenIdx = [];
    let odd = array.filter((x,i) => {
      if(!(x % 2)){
        evenIdx.push(i);
        return false;
      }
      else return true;
    }).sort((a,b) => a - b);
    //자르고 끼워넣고 붙이기
    for(let i = 0; i < evenIdx.length; i++){
      const tmpArr = odd.splice(evenIdx[i]);
      odd = odd.concat(array[evenIdx[i]]);
      odd = odd.concat(tmpArr);
    }
    return odd;
  }

이 풀이는 처음 생각한 Array 메소드를 활용한 풀이였다. 물론 답은 나오는데 뭔가 마음에 들지 않아서 방법을 선회하였던 것이다. 그런데 찝찝함을 한 방에 해결해준 것이 바로 Best Solution의 3번째 라인의 map()과 shift() 메소드였다.

map()은 배열을 순회하면서 콜백함수에서 실행한 결과값을 새로운 배열로 만들어주는 메소드이다. shift()는 배열의 첫번째 요소를 제거하고 그 요소를 리턴해주는 메소드이다.

shift() 에 대해서 조금만 더 알아보자
배열에서 첫번째 요소를 제거하고 제거된 요소를 리턴한다. 원배열을 변형시킨다.(원배열의 길이를 변하게 한다.)
```
		const arr = [1,2,3,4];
		const firstEle = arr.shift();
		console.log(arr); 		// [2,3,4]
		console.log(firstEle) 	// 1
```
빈 배열인 경우, undefined를 리턴한다.

위 두가지의 메소드의 결합으로 내가 만든 일명 배열을 자르고 끼워넣고 붙이기의 작업을 할 수 있었다. 나의 생각은 홀수만 필터링한 배열에 어떻게 짝수를 끼워 넣는냐 였다. 그런데 이 친구의 생각은 완전히 새로운 배열을 만들자 였던 것 같다. 기존 배열을 순회시키면서 짝수일 때는 기존 배열에서 요소를 가져오고 짝수가 아닌 경우에는 odd라는 필터링한 배열에서 요소를 shift()를 이용해서 요소를 차례차례 가져왔다. 순회가 끝나면 map()의 리턴값으로 새로운 배열이 나온다. 굳이 concat()을 반복하면서 붙일 필요가 없다.