[분석] Codility - PermMissingElem - Javascript

Codility 연습문제 > PermMissingElem > Javascript
주어진 순열에서 누락된 요소를 찾는 문제.

실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

N개의 다른 정수로 구성된 배열 A가 제공됩니다. 배열에는 [1 .. (N + 1)] 범위의 정수가 포함되어 있습니다. 즉, 정확히 하나의 요소가 누락되어 있는 배열에서 누락된 요소를 찾아 반환해야 합니다.

1. 배열의 요소는 0 index 부터 순차적으로 증가하는 숫자이다.
2. 배열에는 순차적으로 증가하지 못한 누락된 요소가 포함되어 있다.
3. 예를들어, A = [2, 3, 1, 5] 의 배열에는 4의 값이 누락되어 있다.
4. 함수는 배열내 누락된 값을 찾아 반환해야 한다.
   
   

[분석]

1. 배열의 길이는 0 ~ 100,000 내의 정수이다.
2. 배열의 각 요소는 구별된다.
3. 배열의 각 요소는 1 ~ N + 1 의 범위를 갖는 정수이다.
4. 배열의 길이가 0일 수도 있으므로 빠른 결과 반환이 필요하다.
   
   

[풀이]

1. 배열의 순서는 1씩 증가하지만 요소중에 누락된 값이 있을 수 있다. (1, 2, 4, 5 => 3 누락)
2. 오름차순 정렬로 배열 요소들을 정렬해야 누락값을 찾기 편하다.
3. 결과값 뿐만아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야합니다.

function solution(A) {
  // 요소의 최대 범위는 N + 1 이다. 최대값은 배열 길이의 +1 이 된다.
  // 배열의 마지막 값이 빠질수도 있다.
  let result = A.length + 1;
  // 오름 차순 정렬을 한다.
  A.sort((a, b) => a - b);

  for (let i = 0; i < A.length; i++) {
    // index 와 값은 +1 차이다.
    if (A[i] !== i + 1) {
      result = i + 1;
      break;
    }
  }

  return result;
}

[마치며]

PermMissingElem 문제의 경우 배열의 길이와 각 값의 숫자 범위에 대해서 잘 이해하고 문제를 풀어야 합니다. 단순하게 기준값 다음이 +1의 값이므로 만약 아니라면 +1한 값이 누락 값이라고 판단해 문제를 풀 수 있습니다. 문제의 핵심은 index 와 값의 연관성을 파악하고 index + 1의 값이 다른 값을 누락 값으로 반환해야 합니다.