Codility - Lesson 4 : MissingInteger

 

  조금 골치를 썩인 문제였다.

 

  처음에 시도한 방식은 우선 10만 칸의 boolean 배열을 만들고, A를 순회하며 배열 칸의 값이 자연수일 경우 10만칸의 배열에 해당하는 칸을 true로 셋팅을 하는 것이었다. 또, A의 min 값과 max 값을 찾아낸 다음 max 값이 1보다 작으면 1을 return, min 값이 1보다 크면 1을 return을 해줬다. 이후 배열의 1번 째 칸부터 순회하면서 false인 값을 찾아내는 순간 최종 답으로 return을 하도록 했었는데... 이렇게 하니 성능 체크 테스트 케이스에서 시간 초과가 0.05초 정도 발생하면서 fail이 됐다.

  내 생각엔 이 알고리즘은 O(n) *2 정도의 시간 복잡도였는데 실제 시간 복잡도는 더 컸던 모양이었다.

  

 

  그래서 다른 방식이 필요하다고 생각을 했고, 결국 아래와 같은 전통의 정렬 방식을 이용하기로 했다.

function solution(A) {     const sorted = [...new Set(A)].sort(function(a, b) {         return a - b;     });     if (sorted[sorted.length - 1] < 1) {         return 1;     }     if (sorted[0] > 1) {         return 1;     }     let lastNum = sorted[0];     for (let index = 1; index < sorted.length; index += 1) {         if (sorted[index] < 1) {             continue;         }         if (sorted[index] > 1) {             if (lastNum < 1) {                 return 1;             }             if (sorted[index] > lastNum + 1) {                 return lastNum + 1;             }         }         lastNum = sorted[index];     }     return lastNum + 1; }

 

  정렬 방식으로 문제를 풀다가 계속 테스트 케이스에서 실패가 나서 당황했었는데, 디버깅을 하다보니 첫 번째 줄에 있는 sort 함수의 사용에 문제가 있었음을 깨달았다. 그냥 sort() 함수를 사용하면 text 비교를 하게 되는 것이었다. 예를들어 [1, 2, 1000] 라는 배열을 sort()로만 하게 되면 [1, 1000, 2]가 나오게 된다. 이를 막으려면 반드시 위와 같이 숫자로서 sort를 하도록 해줘야 한다.

 

  혹시나 해서 다른 사람들의 풀이법도 비교해봤는데 대체로 sort를 한 뒤 문제를 해결하는 것 같았다.

 

  결과