2018-11-17
[JS] Max Counters
MEDIUM

개요

정수 N으로 채워진 배열 A가 주어집니다. 배열은 홀수로 채워져있습니다. 각 요소는 같은 값을 가진 짝이 있습니다. 단 하나의 요소만 짝이 없습니다.

예시

A[0] = 9  A[1] = 3  A[2] = 9
A[3] = 3  A[4] = 9  A[5] = 7
A[6] = 9
  • 0, 2번 index는 같은 값 9를 가집니다.
  • 1, 3번 index는 같은 값 3을 가집니다.
  • 4, 6번 index는 같은 값 9를 가집니다.
  • 5번 index는 값 7을 가지고, 짝이 없습니다.

문제

배열 A가 주어질 때, 짝이 없는 값을 반환하세요.

제한

  • 배열 A의 길이 N은 1 ~ 1,000,000 범위를 가집니다.
  • 각 요소의 값은 1 ~ 1,000,000,000 범위를 가집니다.
  • 단 하나의 요소를 제외하고는 짝이 있습니다.

풀이

스코어 66% (정확도 100%, 성능 25%)

function solution(A) {
  for (let i = 0; i<A.length; i++) {
    if (A[i] !== 0) {
      // 마지막까지 잡히지 않았다면 현재 위치가 짝이 없음
      if (i === A.length - 1) {
        return A[i]
      }
      
      // A[i+1]부터 마지막까지 A[i]랑 일치하는 값들을 고름
      let count = 1;
      let index = -1;
      let val = A[i];
      for (let j = i+1; j<A.length; j++) {
        if (A[j] === A[i]) {
          A[j] = 0;
          count++;
          index = j;
        }
      }
      
      // 만약 index가 -1이면 A[i]가 짝이 없음
      if(index === -1) {
        return val
      }
      
      // 만약 count가 홀수면 마지막 같은 값이 짝이 없음
      if (count % 2 === 1) {
        return val
      }
    }
  }
}

최적화 전의 코드입니다. 시간복잡도는 O(N**2) 입니다.
아이디어는 이렇습니다:

  • 이중배열을 통해 i번째 요소와 일치하는 모든 값을 0으로 만든다.
  • 만약 이번 순회에서 0으로 만든 값의 개수가 홀수라면, 짝이 없는 값이다.
  • 0으로 초기화 했기 때문에 0이면 순회를 건너뛴다.
  • 만약 0으로 초기화한 값이 없으면 짝이 없는 값이다.
  • 마지막 요소까지 도달했다면 마지막 요소가 짝이 없다.

이렇게 짜고 나니 도저히 최적화 할 수 있는 방법이 떠오르지 않아 검색으로 성능 최적화 된 코드를 찾을 수 있었습니다.

스코어 66% (정확도 100%, 성능 25%)

function solution(A) {
  let result = 0;

  for (let element of A) {
    // Apply Bitwise XOR to the current and next element
    result ^= element
  }

  return result
}

코드출처: https://gist.github.com/K0ff33/3eb60cfb976dee0a0a969fc9f84ae145

설명

^=XOR 비트 연산자입니다. XOR 비트 연산은 대응하는 각각의 비트가 서로 다를 때만 1을 반환합니다.

예를 들어, 9를 2진수로 변환하면 1001입니다.
그렇다면 9 ^= 9는 어떤 값이 나올까요?
10011001의 각 자리수의 비트는 모두 같으므로, 반환 값은 0000이 됩니다.

다시 말해, 짝이 있다면 배열의 연산 결과는 0000으로 소거되고, 짝이 없는 수가 남습니다.

이 문제의 난이도가 PAINLESS/EASY인 것이 조금 충격적입니다. 이럴 때 CS전공을 하지 않은 것이 후회됩니다.