PermMissingElem

/Codility

문제 해석

요약

이미 풀어본 leetcode의 Missing Number와 거의 같은 문제이다. 다른게 있다면, 0이 아닌, 1부터 시작한다는 점!!!

전문

🇰🇷 번역

N개의 다른 정수로 이루어진 배열 A가 주어진다. 그 배열에는 [1..(N + 1)]범위의 정수를 포함하는데, 그 의미는 정확히 하나의 요소가 사라졌다는 것을 의미한다.

당신의 목표는 사라진 요소를 찾는 것이다.

함수를 작성하시오:

function solution(A);

배열 A가 주어졌고, 누락된 요소를 반환하라.

A가 다음과 같이 주어진다면:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5

함수는 누락된 요소로 4를 반환해야한다.

다음과 같은 가정에 따라 효율적인 알고리즘을 작성하시오:

  • N은 범위가 [1..1,000] 사이인 정수이다;
  • A의 각 요소는 모두 구별된다;
  • A의 각 요소는 [1..(N + 1)] 범위인 정수이다.

🇺🇸 원문

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

function solution(A);

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [0..100,000];
  • the elements of A are all distinct;
  • each element of array A is an integer within the range [1..(N + 1)].

🤔 문제 해결 방법 구상

이제 익숙하다! 중복된 숫자 찾기, 짝 안맞는 숫자찾기류의 문제는 비트연산자 XOR을 사용하면 간단하다.

  1. 빠진부분을 찾기에 가장 편리한 방법은 첫번째 위치에 1이 있는 것이다.
  2. 이점을 이용하여 XOR로 비교한다.
  3. 즉, for문에서 위치 ^ 값을 전체 배열에 적용하면, 결국 짝이없는 하나만 남을 것이다.
  4. 다만 이 문제에서 주의해야 하는 점은, 0부터 시작이 아니라 1부터 시작한다는 점이다.

코드 구현

function solution(A) {
  let checked = 0;

  let realLength = A.length + 1;
  for (let i = 1; i <= realLength; i ++) {
    checked ^= i ^ A[i - 1];
  }

  return checked;
};

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

시간 복잡도는 O(n) 또는 O(N * log(N))으로 나온다. 공간 복잡도는 O(1)으로 예상한다.

🤔 또 다른 방법

개선이라기 보단, 총합에서 현재 있는 숫자의 합을 빼는 식으로 계산하는 가우스 계산법도 이용해 보았다.

또 다른 코드

function solution(A) {
  const l = A.length + 1;
  const total = (l * (l + 1)) / 2;
  const add = A.reduce((acc, cur) => acc + cur);

  return total - add;
}

또 다른 결과

Task Score: 90%
Correctness: 80%
Performance: 100%

오오?😳 100%가 아니라니!
시간 복잡도는 똑같이 O(n) 또는 O(N * log(N))으로 나온다. 마찬가지로 공간 복잡도는 O(1)으로 예상한다.

퍼포먼스가 아닌, 정확도에서 점수가 낮게 나왔다.
오류가 나는 부분은 바로!
emptyandsingle 테스트 부분이었다.
empty list and single element로 비어 있거나 하나의 요소만 있을때 테스트에서 RUNTIME ERROR가 발생하였다. 새로운 코드에서 사용한 reduce에 initial value가 없어서 나는 오류이다.

🧐 개선

A가 없거나 길이가 0일 때, 예외사항을 적용해 주면 간단히 해결될 것 같다.

개선 코드

function solution(A) {
  if (!A || A.length === 0) return 1;
  const l = A.length + 1;
  const total = (l * (l + 1)) / 2;
  const add = A.reduce((acc, cur) => acc + cur);

  return total - add;
}

개선 결과

Task Score: 100%
Correctness: 100%
Performance: 100%

1부터 시작한다고 가정했으므로, 길이가 0인 배열에서 누락된 값은 1로 반환한다.

마무리

많이 풀어본 문제라 쉽게 풀었지만 실수를 했다. 시작되는 숫자와 같은 조건은 항상 잘 파악해야하고, 간단한 예외 케이스의 경우는 앞부분에서 미리 처리해 주는 것을 잊지 말자.

Reference & Learn More

Missing Number

Tags
Comments