Find the unique number<6 kyu>

문제링크

문제

There is an array with some numbers. All numbers are equal except for one. Try to find it!

• findUniq([ 1, 1, 1, 2, 1, 1 ]) === 2
• findUniq([ 0, 0, 0.55, 0, 0 ]) === 0.55
• It’s guaranteed that array contains at least 3 numbers.

The tests contain some very huge arrays, so think about performance.

🚩 문제해석
아주 단순하다. 배열 중에서 값이 다른 요소가 하나 있는데 그것을 찾아라! 라는 것이다. 아주 큰 배열이 들어올 때의 성능(효율성)에 대해서도 생각하라고 한다.

문제접근

• 알고리즘 문제 중에서 일명 이름이 붙어있는 문제들, 예를 들어 DP(다이나믹프로그래밍), 그래프, 백트랙킹 등등 그런 문제들이 아닌 길지 않은 문제들을 접하다보면 해당 언어에 대한 기본적인 프로그래밍에 익숙해지는 것 같다. 이런 문제도 마찬가지이다. 엄청 고차원의 문제는 아니기 때문에 자바스크립트의 배열 메소드를 이용해서 풀면 되겠다라는 생각에서 접근하기 시작했다. 처음에는 every() 메소드로 접근했다.
  - every(callback) : 배열을 순회 할 때 판별함수인 콜백함수가 모두 true를 나타낼 때, true값을 리턴하고 하나라도 false가 나온다고 바로 빠져나와 false를 리턴해준다.이렇게 생각하면 사용할 수 있는거 아닌가 라고 생각하지만 every의 리턴값은 boolean이기때문에 혼자만 다른 그 값을 찾아서 리턴해야하는 이 문제에서는 사용하기가 부적절하다는 결론을 내렸다.

나의 풀이

  function findUniq(arr) {
    let findNumber;
    arr.forEach(function(ele){
      if(arr.indexOf(ele) === arr.lastIndexOf(ele)){
          findNumber = ele;
          return
      }
    });
    return findNumber;
  }

'배열의 모든 요소를 다 순회해서 비교하는 방법 밖에 없나' 라는 생각을 극복하기 위해서 여러가지 메소드나 방법들에 대해서 생각해봤는데, 역시 비교 할 수 밖에 없었다. 그래서 위의 코드처럼 indexOf()와 lastIndexOf()를 사용하여서 문제를 풀이하였다. 우선은 사이트에서 주어지는 모든 테스트 샘플은 통과하였다. 하지만, 위 코드는 사실 성능면, 속도면에서 그렇게 좋다고 생각하진 않는다. indexOf()와 lastIndexOf()가 모두 실행할 때마다 배열을 1번씩 다 확인한다. 그것도 forEach()안에서 그런 메소드가 실행되기 때문에 O(n^2)라고 볼 수 있다. 코드가 마음에 들지는 않지만 결과는 통과이기 때문에 우선 넘어간 후 다른 좋은 풀이들에 대해서 살펴보았다. 그리고 Array 메소드들의 기저에서 돌아가는 원리, 개념들에 대해서 찾아보고 분석하는 것도 좋은 테마거리라고 생각한다. 그 부분에 있어서도 찾아서 정리해봐야겠다.

Best Solution

  function findUniq(arr) {
    arr.sort((a,b)=>a-b);
    return arr[0]==arr[1]?arr.pop():arr[0]
  }

깜박 잊고 있었다. 정렬에 대해서...뭔가 빨리 검색하고 빨리 찾기 위해서 정렬을 하면 좀 더 쉽고 빠르게 할 수 있다는 것을. 물론 어떻게 정렬하는가에서도 소모값이 들어가기 때문에 그 부분에 있어서도 생각해야할 문제일 수 있다. 하지만 여기서는 정렬을 하여 해결을 하면 좀 더 빠르게 해결 할 수 있다. 그와 더불어 이 부분 return arr[0]==arr[1]?arr.pop():arr[0]에 대한 아이디어는 굉장히 센스 있는 코드인 것 같다. 이런 부분을 보면 살며시 미소가 지어진다. 내가 한 것도 아닌데 뭔가 재미있고 깨달음의 미소인 건지 아니면 좋은걸 하나 배워서 즐거워하는 미소인 것인지...

결론

남의 코드를 보는 재미가 솔솔하다. 그리고 codewars는 외국사이트라서 그런지 코드들이 뭔가 정형화 되어 있지 않고 자기만의 스타일로 풀어낸 부분들이 많다. 굉장히 쉬운 문제들일지라도 그 안의 코드를 이해하고 더 나아가 왜 코드를 이렇게 만들었는지에 대해서도 생각하다보면 코드를 바라보는 안목이 한층 더 올라갈 것이라고 생각한다.

🚀 문제를 풀어나갈 때 생각의 흐름을 정리합니다. 또한 새로운 풀이에 대한 코드를 분석하고 모르는 부분에 대해서 정리합니다. 생각이 다른 부분에 대한 피드백은 언제나 환영합니다. 틀린 내용에 대한 피드백 또한 항상 감사합니다.