includes vs set + has

✨존재하지 않는 수 찾기

함수는 정수 배열 A가 주어졌을 때, A에 존재하지 않는 가장 작은 양의 정수(0보다 큰)를 반환하는 문제를 풀면서 고민한 내용입니다.

처음에는 단순히 배열을 정렬한 후, 반복문을 사용하여 A에 존재하지 않는 가장 작은 수를 찾도록 코드를 작성했습니다. 정확도는 100%였지만 성능 점수가 25%로 매우 낮아, 제 코드의 문제점을 고민하게 되었습니다.

function solution(A) {
  return A.sort((a, b) => a - b).reduce((acc, cur) => {
    if (!A.includes(acc)) {
      return acc;
    }
    if (acc <= cur) {
      acc = cur + 1;
    }
    return acc;
  }, 1);
}

문제점: includes 메서드의 사용

includes()는 매번 배열을 돌면서 특정 값이 존재하는지 확인합니다. 배열의 길이만큼의 시간이 소요되므로, 이 작업을 reduce 내에서 매번 호출하게 되면 시간 복잡도가 매우 비효율적으로 됩니다.

배열의 길이만큼의 시간이 드는 데, 이 작업을 reduce 내에서 매번 호출하기때문에 시간이 오래걸린다는 것을 알게 되었습니다.

최적화된 접근방법

따라서 includes 대신 Set을 사용하여 중복된 수와 양수만 남긴 후, 1부터 시작하여 존재하지 않는 가장 작은 수를 찾는 방식으로 코드를 개선했습니다.

function solution(A) {
  const setA = new Set(A.filter((num) => num > 0));
  let answer = 1;

  while (setA.has(answer)) {
    answer++;
  }

  return answer;
}

주로 map이나 reduce, for문을 사용하여 반복하는 작업들을 주로 작성하느라 while문을 사용해 존재하는 값을 찾는 것이 매우 효율적이라는 점을 깨달았습니다. 특히, 배열이 길 경우 Set과 같은 자료구조를 활용하여 처리하는 것이 성능 면에서 유리하다는 것을 배웠습니다.