코딜리티(Codility) Lesson3 PermMissingElem 문제풀기

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

문제 해결:

1. 숫자 배열에 [1 ... 배열개수 +1] 범위 숫자가 임의적으로 들어가있다.

2. 임의적으로 들어가있는 숫자중에 놓친 값이 있는지 찾아라.

나의 생각: 배열의 인덱스와 값을 맞추자.

즉, A[0] =1 , A[1] = 2 ,  A[2] = 3,  A[3]= 5 이렇게 만들어 놓고 

A[3] = 5 부분에 값에 4가 들어가야되므로 return 4를 하면 되지 않을까?

function solution(A) {
    //빈값 경우 <== 이걸 안해서 점수가 처음에 깎였다.
    if(A.length === 0) return 1;
    
	// sort함수로 배열 정리
    const sortArr = A.sort((a,b) => a-b);
    
    // 정렬된 배열값과 (배열 index + 1) 다를 경우
    for(let i=0; i< A.length; i++){
        if(sortArr[i] !== i+1) return i+1;
    }
	
    // 끝에 있는 경우
    return A.length +1;
}

 

하지만 역시나 여기서 끝이 아니라 다른 사람들 코드를 봐야 다른 시야가 좋아지지 않을까?

역시나 깔끔하게 처리하신 고수분이 있으셨다. 고수님 블로그에 설명도 친절하게 적어두셨다.

function solution(A) {
    if (A.length === 0) {
        return 1;
    }
    return (((A.length + 2) * (A.length + 1)) / 2) - A.reduce(function(accumulator, currentvalue) {
        return accumulator+currentvalue;
    })
}

jaewc.github.io/algorithm/2018/08/07/PermMissingElem/