[분석] Codility - MissingInteger - Javascript

Codility 연습문제 > MissingInteger > Javascript
주어진 시퀀스에서 발생하지 않은 가장 작은 양의 정수를 찾는 문제.

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

[문제 및 조건]

N 개의 정수 배열 A가 주어지고 A에서 발생하지 않은 가장 작은 양의 정수 (0 보다 큼)를 반환하세요.

1. 정수 배열 A 가 주어진다.
2. 배열 내 정수중 0 보다 큰 값중에 발생하지 않은 정수 값을 찾아라.
   
   

[분석]

1. N 은 1 ~ 100,000 범위 내의 정수이다.
2. 배열 A의 각 요소는 -1,000,000 ~ 1,000,000 범위 내의 정수이다.
3. 배열의 요소는 순차적은 증가 패턴을 가지고 있다.
4. 만약 [1, 2, 3] 이 주어지면 4를 반환하고, [-1, -3] 이 주어지면 1을 반환해야한다.
5. 발생하지 않은 값이 음수라면 무조건 1을 반환한다.
   
   

[풀이]

1. 배열 A를 오름차순으로 정렬한다.
2. 최소, 최대값을 구해 유효범위를 먼저 확인한다.
3. 1보다 큰 요소들이 나열되었다면 1을 반환, 모든 요소가 순차적으로 나열되어 있지만 맨 마지막 요소 + 1 의 값을 반환해야한다.
4. 모든 요소들이 음수라면 1을 반환한다.
   
   

function solution(A) {
  // 중복 숫자를 제거하고 오름차순으로 정렬한다. 
  // 그리고 양의 정수만 필터링한다.
  const numbers = [...new Set(A.sort((a, b) => a - b))]
    .filter(val => val > 0);
  const min = numbers[0];
  const max = numbers[numbers.length - 1];
  let result = 1;

  // 1이 없거나, 빈 배열(음수 요소들 필터링)이면 1을 바로 반환한다.
  if (min > 1 || numbers.length < 0) {
    return 1;
  }

  // 양의 요소 집합인 경우, 최대 최소의 값과 
  // 배열 길이가 같은 순차 증가 배열이면 최대값 + 1 을 반환한다.
  if ((max - min) + 1 === numbers.length) {
    return max + 1;
  }

  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i] + 1 !== numbers[i + 1]) {
      result = numbers[i] + 1;
      break;
    }
  }

  return result;
}

분석과 풀이를 바탕으로 1차 코딩한 함수는 정답과 성능 테스트를 모두 통과하였습니다. 결과적으로 시간 복잡도는 O(N) 또는 O(N * log(N))으로 나쁘지 않았지만 최초 배열을 가공하고 예외 처리한 항목 때문에 함수의 길이가 길어지고 말았습니다. 중복 요소를 제거하기 위해 사용한 Set 함수 및 0 이하 요소를 제거하는 filter 함수를 사용하지 않는 방향으로 다시 코딩해 보았습니다.

function solution(A) {
  // 기본 반환되는 수는 1로 지정합니다.
  let result = 1;
  // A 배열을 오름차순으로 정렬합니다. 
  // 물론 중복 숫자가 포함될 수 있습니다.
  A.sort((a, b) => a - b);

  for ( val of A) {
    val === result && result++;
  }

  return result;
}

결과는 O(N) or O(N * log(N))의 시간 복잡도가 나왔습니다. 이 문제는 두 개 이상의 반복문을 중첩으로 사용하지 않는다면 성능 테스트에서 크게 문제가 되지 않는 것 같습니다. ECMA6에서 도입된 for of를 이용해 값을 바로 비교하고 누락 요소를 정의하는 코드를 사용하니 길이가 상당히 짧아졌습니다.

[마치며]

MissingInteger 문제는 시간 복잡도가 크지 않다면 모든 풀이가 가능해 보입니다. 앞으로는 중첩된 반복문을 사용하지 않고 풀이할 수 있다면 되도록이면 코드라인을 짧게 가져가는 방향으로 접근해야할 것 같습니다.