PermMissingElem

[dlehdanakf]

개요

• Codility 사이트에서 문제를 풀다가 어이없는 실수로 한번에 해결하지 못한 문제
• 오답노트로 만들어두면 다음번엔 같은 실수 안하겠지 (아마도)
• 문제 바로가기
• 숫자 N이 주어지고 배열이 넘어온다.
• 배열 속에는 1 부터 N + 1 까지의 숫자가 있고, 당연 N + 1 까지인 만큼 중간에 한 숫자는 비어있다. 빠진 숫자를 구하는 문제!

오답내용

• 정렬되지 않은 input 에 대해 배열을 정렬한 다음 index 와 value - 1 값이 서로 일치하지 않는 요소를 찾으려고 했다.
• 언듯 보면 맞는 방법인듯 하다.

0	1	2	3	4
1	2	4	5	6

• 위와 같이 숫자 3이 없을 경우 바로 찾는 것이 가능하다. 5분만에 코드를 작성하고 제출했다.

• 하지만 채점을 돌려보니 전체 테스트케이스 중 절반만 통과했다... 생각해보니 반례가 많았다.

  • 배열의 길이가 1일 경우
  • 배열에 원소가 없을 경우
  • 1 또는 N 이 없는 경우

• 다른 방법도 사용해봤다.

• 길이가 N 인 배열을 만들고 모두 false로 초기화한다.

• 배열을 돌면서 해당 값을 인덱스로하여 N 배열의 값을 적절히 true로 변환한다.

• 최종적으로 false 인 값을 리턴한다.

function solution(A) {
    const N = new Array(A.length).fill(false);
    for(let i = 0; i < A.length; i++) {
        N[A[i] - 1] = true;
    }

    return N.indexOf(false) + 1;
}

• 문제는 위 코드도 틀렸다는거다...
• 위 코드는 [1, 2, ... , N + 1] 범위의 배열에서 빠진 숫자가 N + 1 일 경우를 찾지 못한다.
• 따라서 아래와 같이 배열을 선언할 때 한 칸을 더 선언해줘야한다.

function solution(A) {
    const N = new Array(A.length + 1).fill(false);
    for(let i = 0; i < A.length; i++) {
        N[A[i] - 1] = true;
    }

    return N.findIndex(e => e === false) + 1;
}