Codility - PermMissingElem 풀이

Lesson3. PermMissingElem

안녕하세요!

저번 시간에는 Lesson3. FrogJmp에 대해 풀이해봤습니다.

이번에는 Lesson3의 PermMissingElem를 풀이해보려 합니다.

Question

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

PermMissingElem coding task - Learn to Code - Codility

N 개의 서로 다른 정수로 구성된 배열 A가 주어지는데 ( [1...(N + 1)]의 범위의 정수 배열 ) 이 때, 정확히 한 개의 요소만 누락되어 있습니다.

우리는 그 누락된 요소를 찾으면 됩니다.

 

만약, 주어진 배열 A가 [1, 3, 2, 4] 이라고 할 때, 정상적인 범위의 배열은 [1, 2, 3, 4, 5] 입니다.

배열 A에는 5라는 요소가 빠져있으므로, 5를 반환해야 합니다!

Answer

예전에 객체를 활용해서 풀이했던 것 처럼 이번에도 비슷하게 구현해봤습니다.

 

1. 정상적인 정수 범위의 배열을 객체로 만듭니다.

2. A 배열에 대해 루프를 돌며, 객체의 키 값이 undefined가 아닌 경우 (= 존재할 경우) 해당 객체 키를 delete 시켜줍니다.

3. 정확히 한 개의 요소만 누락되었으므로, 객체에는 단 하나의 키와 값이 남게 됩니다.

4. 객체의 값을 배열로 변환하여 가장 첫 번째 요소를 반환하면 해결할 수 있습니다.

 

풀이 코드는 아래와 같습니다. ( 시간 복잡도는 O(N) 혹은 O(N log N) )

function solution(A) {
  const formattedObj = {};
  const arrLeng = A.length;
  
  for (let cnt = 1; cnt <= arrLeng + 1; cnt++) {
    formattedObj[cnt] = cnt;
  }
  
  for (let idx = 0; idx < arrLeng; idx++) {
    const value = A[idx];
    
    if (formattedObj[value] !== undefined) {
      delete formattedObj[value];
    }
  }
  
  return Object.values(formattedObj)[0];
}

 

풀이 결과

The End

문제는 그다지 어렵지 않았지만, 초반에 이해를 제대로 하지 못 해 불필요한 정렬이나 루프를 도는 등의 코드를 짰었습니다.

잘 해결되긴 했지만, 앞으로 좀 더 주의해서 코드를 짜야겠다는 생각을 했습니다.

다음 시간에는 Lesson3의 마지막 문제인 TapeEquilibrium에 대해 풀이해보려 합니다.

봐주셔서 정말 감사합니다!