Smallest unused ID, includes() has() indexOf() new Set() | Codewars [자바스크립트]

Codewars 8kyu 문제 Smallest unused ID.

Codewars: Achieve mastery through challenge

숫자로 이뤄진 배열이 주어지고 배열에 들어있지 않은 가장 작은 숫자를 찾는 문제.

 

7kyu로 넘어갈까 생각하고 있었는데 힘겹게 풂. 그런데 항상 그렇듯 답변을 보니 너무나 간단.

 

처음에 코드를 어떻게 썼는지 기억이 안 나지만 간단하게 짜보려다가 자꾸 NaN이나 undefined가 나옴.

 

그래서 우선 입력값 중에서 최소값을 찾는 메소드를 만들고

Array.min = function (array) {
  return Math.min.apply(Math, array);
}

이걸 이용해서 코드를 써봄.

function nextId(ids) {   
  let minValue = Array.min(ids);
  let nextMinValue;

  if (minValue !== 0) {
    return 0;
  } else {
    while (ids.length > 0) {
      ids.splice(ids.indexOf(minValue), 1);

      nextMinValue = Array.min(ids);

      if (nextMinValue !== minValue && nextMinValue !== minValue + 1) {
        break;
      }

      minValue = nextMinValue;
    }
  }

  return minValue + 1;
}

최소값이 0이 아니면 0을 찍어내고

최소값이 0일 땐 최소값 지우기 -> 다음 최소값 찾기 -> 다음 최소값이 기존 최소값과 같거나 1 크다면 기존 최소값을 다음 최소값으로 대체하기 -> 최소값 지우기 반복

다음 최소값이 기존 최소값과 간격이 벌어져 있다면 기존 최소값 +1 찍어내기.

 

그런데

테스트 가운데 일부가 자꾸 틀리다고 나옴.

 

함수 제일 위쪽에 console.log(ids)를 추가해서 입력값을 살펴보니

이렇게 정답이 이상하게 0으로 정해진 테스트들이 있음.

 

Discuss를 들여다보니 비슷한 문제에 부딪힌 사람들이 보임.

It could also be that yor're mutating the input and that causes problems라고.

 

코드가 잘못된 것 같진 않은데 어쨌든 입력값을 변환하지 말라니까 다른 방법으로 써봄.

function nextId(ids) {
  const sortedIds = ids.sort((a, b) => a - b);
  
  let minValue = sortedIds[0];
  let nextMinValue;
  
  if (minValue !== 0) {
    return 0;
  } else {
    for (let i = 0; i < ids.length; i++) {
      minValue = sortedIds[i];
      nextMinValue = sortedIds[i + 1];
       
      if (nextMinValue !== minValue && nextMinValue !== minValue + 1) {
        return minValue + 1;
      }
    }
  }
}

입력값을 오름차순으로 정렬하고 앞에서부터 요소를 두 개씩 비교. 결과는 성공.

 

그러고 다른 사람들의 답변을 보니 내가 쓸데없이 어렵게 풀었다는 생각이 듦.

 

우선

function nextId(ids){
  for (i = 0; i < ids.length; i++) { 
    if (ids.indexOf(i) === -1){
      return i;
    }
  }
  
  return ids.length;
}

효율성과 별개로 이 정도는 생각할 만한 듯.

입력값의 길이만큼 0부터 인덱스를 검토해서 없으면 해당 인덱스를 찍어내고 끝까지 돌면 length, 즉 최대값 +1을 돌려냄.

 

또 한 가지는

 function nextId(ids){
  let i = 0;
  while (ids.includes(i)) i++;
  return i;
}

includes()는 배열에 해당 값이 있는지 확인해서 불리언값을 찍어내는 메소드.

0부터 찾아서 있으면 +1, 없으면 그 값을 리턴, 끝까지 있으면 1 더한 값을 찍어냄.

 

가장 추천을 많이 받은 해답은

function nextId(ids){
  const used = new Set(ids);
  for (let i = 0; i <= ids.length; i++) {
    if (!used.has(i)) return i;
  }
}

new Set()와 has() 공부 필요.

Set

Set.prototype.has()