Moving Zeros To The End<5 kyu>

jjanmo·2020년 1월 10일

문제

Write an algorithm that takes an array and moves all of the zeros to the end, preserving the order of the other elements.

moveZeros([false,1,0,1,2,0,1,3,"a"]) // returns[false,1,1,2,1,3,"a",0,0]

🚩 문제해석
배열 안의 숫자 0을 배열의 끝으로 옮기시오. 단 그 외의 배열안의 요소의 순서는 그대로 유지되어야 한다.

문제접근

첫번째 생각
배열의 끝에 숫자 0을 뽑아서 넣는 것이 기본 골격이니까 indexof(), splice(), push() 이런 식의 메소드를 사용하면 해결할 수 있지 않을까? 숫자 0인 부분을 찾고(indexOf()) 그 부분을 배열에서 뽑아서(splice()) 배열의 끝에 집어넣는다(push()) 혹은 합친다(concat()). 이 순서대로 숫자 0이 존재하는 만큼 반복하면 될 것 같다.
두번째 생각
그런데 굳이 숫자 0만을 뽑아야만 할까? 숫자 0이 아닌 것을 뽑으면 안되나? 이런 생각에서 filter()가 나왔고 filter()를 통해서 숫자 0이 아닌 요소들의 배열을 만들어냈다. 하지만 여기서 약간의 오류(?)가 생겼다.
```
  const arr = [0,"a",0,"b",0,null,0,"c","d",1,false,1,3,[],1,9,{},'',undefined];
	let cnt = 0;
  arr.filter(ele => ele === 0 ? cnt++ : ele); 
  // [ 'a', 0, 'b', 0, 0, 'c', 'd', 1, 1, 3, [], 1, 9, {} ]
```
문제에서는 주어진 배열의 요소의 값 중에서는 숫자 외에도 boolean타입의 true, false 나 빈 배열 [], null같은 것들이 포함될 수 있었다. 위의 코드처럼 작성을 하면 ele = false인 경우 return false가 되어서 false라는 요소는 필터링을 통한 새로운 배열의 원소에서 빠지게 된다. 자바스크립트에서 false를 의미하는 값들(false, null, undefined ...)은 모두 같은 결과를 보여준다. 하지만 문제의 요구사항은 그런 요소들도 순서를 유지해야하기 때문에 위의 코드는 요구사항을 충족시키지 못한다. 사실 이 부분은 filter()와 데이터 타입에 대한 이해가 있었으면 해결 가능했는데 (📖추가설명 밑에서!!) 그 부분을 놓쳐서 이 부분을 해결하기 위한 다른 생각(세번째 생각)을 하게 되었다.
변수 cnt를 사용한 이유는 숫자 0인 요소의 개수를 알아야 나중에 새롭게 생성될 배열(숫자 0이 없는 배열) 에 숫자 0으로만 이루어진 배열을 생성하여 붙일 수 있기 때문이다. 0인 배열을 생성할 때, length로서 cnt를 활용하였다.
세번째 생각 : 최종 제출 코드
각각의 요소에 대해서 타입 검사를 해야하는 것인가? typeof는 피연산자의 자료형을 문자열로 반환하는 연산자이다. 이를 이용해서 number가 아닌 타입은 새로운 배열에 속할 수 있도록 만들었다. 또한 cnt를 이용하여 0인 배열을 생성하였다. 두 배열을 concat()으로 연결하면 원하는 배열, 0이 마지막에 있는 배열이 리턴값으로 완성된다.
```
1  var moveZeros = function (arr) {
2    let cnt = 0;
3    return arr.filter(ele =>{
4                  	if(typeof ele !== 'number') return true;
5                  	else if(ele !== 0) return ele;
6                  	else cnt++;
7					 })
8              .concat(Array.from({length:cnt}).fill(0));
9  }
```
6번째 라인을 보면 여기선 return값을 적어주지 않았다. 자바스크립트에서는 리턴값이 없는 경우는 모두 return undefined으로 인식한다. 즉 return false가 되는 것이고, else에 해당하는 요소들을 다 새로운 배열에서 제외가 된다.

filter()와 데이터타입에 대한 정확한 이해 : 두번째 생각의 연장선!!
✅ 어떻게 0이 아닌 숫자를 필터링 할 것 인가?

아래 코드에서 두가지 함수의 차이점을 생각해보자!

  const arr = [0,"a",0,"b",0,null,0,"c","d",1,false,1,3,[],1,9,{},'',undefined];

  var moveZeros1 = function (arr) {
    let cnt = 0;
    return arr.filter(ele =>{
                  return ele !== 0
              });
    		  // == (ele => ele != 0); 보통 이렇게 사용한다, 비교하기위해서 return을 넣어본 것
  }

  var moveZeros2 = function (arr) {
    let cnt = 0;
    return arr.filter(ele =>{
                  if(ele !== 0) return ele
              });
  }
  
  moveZeros1(arr);
	//[ 'a', 'b', null, 'c', 'd', 1, false, 1, 3, [], 1, 9, {}, '', undefined ]
	moveZeros2(arr);
  //[ 'a', 'b', 'c', 'd', 1, 1, 3, [], 1, 9, {} ]

filter()는 전체배열을 순회하면서 콜백함수(판별함수)의 리턴값이 true이면, 그 순회 중인 요소는 새롭게 생성될 배열의 요소에 포함되지만, 결과값이 false이면 새로운 배열에 포함되지 않는다.즉 moveZeros2에서 콜백함수의 결과값을 ele로 주게 되면, 자바스크립트에서 false를 의미하는 값들이 false로 해석되기 때문에 순회 중인 그 요소는 새로운 배열 안에 들어갈 수 없게 되는 것이다. moveZeros1처럼 바꾸면 내가 생각했던 대로의 새로운 배열이 생성 될 수 있다. moveZeros2에서처럼 if조건문을 넣는 것이 아니라 그 조건 자체를 return값으로 사용하면 그 값이 true면 순회 중인 해당 요소는 배열에 포함되는 것이고 false면 포함되지않는다. 이런 경우엔 조건문을 굳이 사용할 필요는 없다 라는 사실!

✅ 여기서 문제는 cnt라는 변수를 넣어야 한다는 것이다. '0인 요소의 개수를 어떻게 셀 것인가' 라는 문제가 생긴다.

아래 코드는 지금까지 발생했던 문제들에 대해서 해결한 코드이다.

  const arr = [0,"a",0,"b",0,null,0,"c","d",1,false,1,3,[],1,9,{},'',undefined];
	let cnt = 0;
  arr.filter(ele => ele === 0 ? cnt++ && false : true);
	// ['a', 'b', null, 'c', 'd', 1, false, 1, 3, [], 1, 9, {}, '', undefined] 
	// cnt = 4

여기서 논리 연산자에 대해서 조금 더 생각해 볼 필요가 있다.

1️⃣cnt++ VS 2️⃣cnt++ && false

1번인 경우(두번째 생각의 코드), 결과값이 어떻게 될까? 처음에 이렇게만 써도 되는 것 아니야 하는 생각을 했었다. `cnt++`만 사용하는 경우 콜백함수의 결과값인 cnt++를 true 나 false로 해석하게 된다. 자세히 설명해보면, 첫번째 루프에서 요소가 `숫자 0` 이기 때문에 결과값으로 `cnt = 0`이 들어가게 되고 **0은 false**로 해석되어서 그 루프의 요소가 제외된다. 그 이후에 배열에서 0이 나오면 **cnt는 0이 아닌 숫자값을 갖게 되고, 그것은 true**로 해석되기 때문에 `숫자 0`은 새로운 배열에 속하게 된다. 즉 원하는대로 필터가 안되는 결과가 나온다.

2번인 경우, 결과값이 어떻게 될까? 이 경우 논리 연산자의 다른 활용에 대해서 알아야 한다. 논리연산자는 보통 연산의 결과값을 true나 false로 나타내며 조건식에서 많이 사용하여 조건에 따라서 어떠한 코드가 실행되도록 만든다. 그런데 && 와 || 연산자는 사실 피연산자 중의 하나의 값을 반환한다. 즉 boolean이외의 값과 함께 사용하면 boolean값이 아닌 값을 반환할 수 있다.

expr1 && expr2	expr1을 true로 변환할 수 있는 경우, 
					expr2을 반환하고, 그렇지 않으면 expr1을 반환한다.
expr1 || expr2	expr1을 true로 변환할 수 있으면 expr1을 반환하고, 
					그렇지 않으면 expr2를 반환한다.

1번에서 문제였던 것은 첫번째 이후의 0에 대해서 숫자가 true로 해석되기 때문에 0이 새로운 배열에 들어가는 것이였다. 이것을 논리 연산자 && 로 해결할 수 있다. 예를 들어 cnt = 1일 때, 0인 요소를 순회하는 경우, 1++ && false 이런식의 코드가 된다. 이것은 1은 숫자이기 때문에 true로 해석되고 논리연산자에 의해 true로 변환이 가능하기에 위 코드의 최종값은 false를 반환하게 된다. 그러면 첫번째 이후의 0도 콜백함수에서 false가 나오기 때문에 새로운 배열에 들어가지 못하게 되어 원하는 결과값을 얻을 수 있다. (++는 후위연산자이기 때문에 그 행의 연산 끝난 후 진행된다.) 이런 식의 논리연산자의 활용이 생각보다 많이 사용된다. 잘 알아두자!

Best Solution

var moveZeros = function (arr) {
  return arr.filter(function(x) {return x !== 0})
    		.concat(arr.filter(function(x) {return x === 0;}));
}

위 코드는 filter()를 두 번 사용하여서 위에서 설명한 문제점에 대해서 해결하였다. 진짜 단순하고 합리적인 해결책이다. 하지만 이 코드는 배열을 2번 순회하게 된다. 0인 아닌 것을 필터링하고 0인 것을 필터링한다. 만약에 배열의 요소가 1억개라면 총 2억개를 반복해야 한다. 효율성이 떨어질 수 있다는 것이다. 그래서 한 번 순회할 때, 0인 요소도 카운팅하는 것이 더 좋지 않을까 조심스럽게 생각해본다. 결과적으로 위 방법도 내가 겪었던 문제들을 아주 쉽게 해결하는 방법이라 생각한다.

결론

여러가지 문제 풀이 방식들을 확인해보면 내 머리 속에 스쳐지나갔던 생각들을 구현해 놓은 것들이 많았다. 하지만 결론은 구현하지 못했던 풀이다. 무엇인가를 많이 몰라서 못하는 것이 아니라 알고 있지만 정확히 알지 못하거나 무엇인가 작은 오류 때문에 그 풀이를 완성하지 못하는 경우들이 많이 생긴다. 작은 오류가 생겼을 때, 그 오류는 내가 원하는 방식으로 해결하는 것, 그것이 진짜 실력이 아닐까 생각한다. 진짜 실력 향상을 위해서 열심히 노력해보자! 그리고 한가지 더 느낀 것은 오류는 생각보다 기본에 대해서 정확하게 알지 못할 때 나오는 경우가 많은 것 같다. 전교 1등이 항상 하는 말인 "교과서에 충실했어요." 처럼 기본에 좀 더 충실할 필요가 있다. 작은 것이라도 소홀하게 넘겨서는 안될 것이다.