[알고리즘/자바스크립트] 어떤 값의 개수가 홀수인지 판별하기 (Find the odd int)

-해당 문제는 codewars사이트의 level6 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

[문제] Given an array, find the int that appears an odd number of times.

There will always be only one integer that appears an odd number of times.

findOdd([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5]) ==> 5 출력

findOdd([1,1,2,-2,5,2,4,4,-1,-2,5]) ==> -1 출력

[해석] 어떤 배열이 주어졌을 때 홀수번 등장하는 숫자를 구하여라. 홀수번 등장하는 숫자는 딱 하나만 있을것이다.

예를 들어서 [20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5] 이런 배열에 주어졌다고 치면 

모든 숫자가 다 2번씩 등장하지만 오직 숫자 5만 1번 등장한다. 

즉, 5를 뺀 모든 수가 짝수 번 등장하였으나 5만 홀수 번 등장하였으므로 5를 return해야한다.

아ㅏㅏ 푸는 데 정말 오래 걸렸던 문제.

이 문제에서 내가 생각해낸 컨셉은 이렇다.

"먼저 숫자를 하나씩 서치해서 개수를 세고, 개수가 홀수이면 return한다."

내가 제일 처음 썼던 코드는 개수를 세고 나서 

개수 센 숫자는 배열에서 아예 삭제한 후 다시 서치하는 것이었는데

코드는 다음과 같다.

function findOdd(A) {
  for(var i=0; i<A.length; i++) {
    var count = 0;
    var index = A.indexOf(A[i]);
    while(index > -1) {
      count++;
      A.splice(index, 1)
      index = A.indexOf(A[i])
      console.log(A[i], count)
    }
  }
}

이 코드의 문제점은 splice로 삭제를 하고 나면 A배열의 개수가 바뀐다는거다..

for문을 A의 length만큼 반복해야하는데 A배열 자체가 바뀌어버리니까 

거기서 자꾸 오류가 났다.

function findOdd(A) {
  var searchNum = A.reduce(function(av, cv, i, arr) {
    var count = 0;
    var index = A.indexOf(cv)
    // console.log(cv, i, count)
    while(index > -1) {
      count++
      index = A.indexOf(cv, index+1)
    }
    if(count % 2 != 0) {
      console.log(cv, count)
      return cv
    }
  }, A[0])
  return searchNum
}

그리고 나서 만든 코드가 위의 코드이다.

일단 count변수를 선언한다.

그리고 현재 처리되고 있는 요소인 cv를 indexOf()로 index를 구한 후 

그 index가 -1이 될 때까지 count++를 한다.

그러면 cv의 개수를 count에 담을 수 있다.

(index가 구해졌을 때 그 구해진 index+1의 위치부터 다시 index를 구해야 제대로 개수를 구할 수 있다.)

그리고 이 과정에서 count가 홀수이면 cv를 return한다.

이렇게 짜니까 배열 요소의 개수를 모두 구할 수는 있었다.

그러나 자꾸 undefined가 return되서 뭐가 문제인지 정말 한~~참을 고민했다.

function findOdd(A) {
  //숫자를 하나씩 서치해서 개수 세고 개수가 홀수면 return하자..
  var searchNum = A.reduce(function(av, cv, i, arr) {
    var count = 0;
    var index = A.indexOf(cv)
    // console.log(cv, i, count)
    while(index > -1) {
      count++
      index = A.indexOf(cv, index+1)
    }
    if(count % 2 != 0) {
      return cv
    }
    return av
  }, A[0])
  return searchNum
}

해답은 너무 간단한 곳에 있었다..ㅜㅜ

cv를 return시키면 cv의 값이 av로 간다.

왜냐면 reduce함수의 첫번째 인자는 accumulator, 즉 콜백의 반환값을 누적하는 인자이기 때문이다.

그 av를 return시켜주면 searchNum에 담기고

그 searchNum을 return시키면 원하는 숫자가 return된다!

이쯤에서 다시 reduce() 메소드의 개념을 정리해보자면 다음과 같다.

arr.reduce(function(accumulator, currentValue, currentIndex, array) {

}, initialValue)

reduce()함수는 4개의 인수를 가지는데

첫번째 accumulator는 콜백함수의 반환값을 누적하며 최초에는 초기값을 가진다.

currentValue는 현재 처리되고 있는 요소가 들어간다.

currentIndex는 현재 처리되고 있는 요소의 index번호다.

array는 reduce()가 호출한 배열이다.

initialValue는 초기값으로 지정하지 않으면 배열의 첫번째 요소가 들어간다.

function findOdd(A) {
  return A.reduce((av, cv, i, arr) => {
    var count = 0
    var index = A.indexOf(cv)
    while(index > -1) {
      count++
      index = A.indexOf(cv, index+1)
    }
    if(count % 2 != 0) return cv
    return av
  }, A[0])
}

위의 코드를 좀 더 간결하게 표현하면 위와 같다.

다른 사람의 풀이를 보니 비트 연산자 ^를 사용한 매우 간결한 답이 많았는데

^가 무엇을 의미하는지 도통 모르겠다..ㅜㅜ 

비트 연산자 공부 좀 해야겠다..

function findOddInt (A) {
    // Complete the findOddInt function.
    var result;
    var isChecked = []; // 한 번 체크한 숫자는 다시 체크하지 않기 위한 빈배열
    for (var i = 0; i < A.length; i++) {
        if (A[i] in isChecked) {
            continue;
        } else {
            var count = 0;
            var index = A.indexOf(A[i]);
            while (index > -1) {
                count++;
                index = A.indexOf(A[i], index + 1);
            }
            if (count % 2 === 1) {
                result = A[i];
            }
            isChecked.push(A[i]);
        }
    }
    return result;
}

위 코드에서 reduce()를 쓰는 것이 적절치 않아 보인다는 피드백을 받고 코드를 다시 수정해보았다.

게다가 위 코드는 문제점이 있는데,

만약에 배열이 [1, 1, 1, 1, 5]라고 했을 때,

1을 4번이나 무의미하게 검사한다는 점이다.

1 - 1, 2, 3, 4 -> 4번 -> 짝수

1 - 1, 2, 3, 4 -> 4번 -> 짝수

1 - 1, 2, 3, 4 -> 4번 -> 짝수

1 - 1, 2, 3, 4 -> 4번 -> 짝수

5 - 1 -> 1번 -> 홀수 -> 정답

이런 순서로 말이다.

1을 검사했는데도, 1이 나올때 마다 반복해서 검사해야하고 매우 불필요하게 느껴졌다.

그래서 위 코드로 바꿔주었는데,

어떤 숫자를 검사하고 나면 그 숫자를 isChecked라는 빈 배열에 넣는다.

그리고 매번 검사하기 전 숫자가 isChecked라는 배열에 있는지 없는지 검사하여

isChecked라는 배열에 없을 때만 검사를 진행한다.

그러면 아래 로직으로 움직이게 된다.

1 - 1, 2, 3, 4 -> 4번 -> 짝수

1 - isChecked에 1이 있으므로 continue

1 - isChecked에 1이 있으므로 continue

1 - isChecked에 1이 있으므로 continue

5 - 1 -> 1번 -> 홀수 -> 정답

function findOddInt (A) {
    // Complete the findOddInt function.
    var isChecked = []; // 한 번 체크한 숫자는 다시 체크하지 않기 위한 빈배열
    for (var i = 0; i < A.length; i++) {
        if (isChecked[A[i]]) {
            continue;
        } else {
            var count = 0;
            var index = A.indexOf(A[i]);
            while (index > -1) {
                count++;
                index = A.indexOf(A[i], index + 1);
            }
            if (count % 2 === 1) {
                return A[i];
            } else {
                isChecked.push(A[i]);
            }
        }
    }
}

다시 2차로 피드백을 받고 코드를 수정하였다.

if (A[i] in isChecked) 구문을 if (isChecked[A[i]])로 바꾸는 것이 더 명확할 것 같다고 하여 수정하였다.

그러고보니 저렇게 쓸 수 있었는데, 왜 A[i] in isChecked 밖에 생각해내지 못했는지ㅜㅜ

그리고 저번에 수정한 코드의 문제점은 

if (count % 2 === 1) {} 이 구문에 걸리는 순간 이미 답이 되는 것이므로 거기서 바로 return시켜주면 되었는데

굳이 모든 숫자를 다 탐색하고 나서 마지막에 결과를 return했다는 점이다.

그래서 result 변수를 지우고 바로 if (count % 2 === 1) {} 구문에 return문을 넣었다.

덧붙여 특별한 경우를 제외하고는 대문자를 변수/매개변수 이름으로 쓰는 경우는 없다고 하셨다(!)

이 부분에 주의해서 앞으로는 꼭 소문자로 적도록 해야겠다.