[알고리즘/자바스크립트] Codility, OddOccurrencesInArray 문제 풀이

Codility, OddOccurrencesInArray

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

• the elements at indexes 0 and 2 have value 9,
• the elements at indexes 1 and 3 have value 3,
• the elements at indexes 4 and 6 have value 9,
• the element at index 5 has value 7 and is unpaired.

Write a function:

function solution(A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

 

 

---

 

 

오늘 푼 문제는 쉬운 난이도의 배열 관련 문제이다.

홀수들로 이루어진 배열이 주어지며 빈 배열은 없다고 가정했을 때,

모든 배열의 요소들은 딱 하나의 요소를 제외하곤 모두 짝을 이룬다.

 

즉, A 배열이 [9, 3, 9, 3, 9, 7, 9]라면 모든 배열의 요소가 짝수 번 등장하는데 7만 홀수 번 등장한다.

이 때 7을 리턴하는 함수를 만들면 된다.

 

즉, A 배열의 요소 중 짝수 번 등장하는 숫자 하나를 리턴하는 함수를 만드는 문제이다.

 

 

 

내가 푼 방법은 다음과 같다.

 

function solution(A) {
  const totalCounter = A.reduce((counter, num) => {
      counter[num] = counter[num] ? counter[num] + 1 : 1;
      return counter;
  }, {});
    
  for (key in totalCounter) {
      if (totalCounter[key] % 2 === 1) {
          return Number(key);
      }
  }
}

 

reduce 메소드를 사용하여 모든 요소의 개수를 센 카운터 객체를 만든다.

객체를 순회하며 카운트 횟수가 홀수인 숫자 하나를 찾아 리턴한다.

 

 

 

 

codility는 문제를 풀고나면 이렇게 시간복잡도를 보여줘서 좋은 것 같다.

시간 복잡도는 O(N) 또는 O(N*logN)이라고 계산되었다.

 

처음에는 배열의 길이만큼 순회하고 그 다음 다시 배열의 길이만큼 순회하지만

홀수번 등장하는 숫자가 발견되면 순회를 멈추기 때문에 시간복잡도는 O(N) 또는 O(N*logN)이 된다.

 

 

 

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility