[Codility] PermMissingElem

문제 

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

PermMissingElem coding task - Learn to Code - Codility

---

처음에는 놀랍게도 50점 밖에 안맞았다.

정렬하고, 배열을 돌면서 인덱스 번호가 인덱스 번호+1 값이 아닌 것을 찾기.

푸는데 5분도 안걸렸을 정도로 쉽다고 생각했는데.... 깜빡한 조건이 있었다.

 

일단 50점짜리 코드를 보자.

class Solution {
    public int solution(int[] A) {
        int lengthOfA = A.length;
        int answer = 0;

        Arrays.sort(A);
        for(int i=0;i<lengthOfA;i++) {
            if(A[i]!=i+1) {
                answer = i+1;
                break;
            }
        } return answer;
    }
}

i번째 값이 i+1이 아닌 경우에는 answer에 넣고 그를 반환했다.

내가 깜빡한 부분은 'N+1 이하' 값에 대한 조건...

 

만약 if문에 걸릴 필요없이 for문을 다 돈다면?

예를 들어 {1,2} 이런 배열이 존재할 때, for문은 if조건에 걸리지 않고 끝까지 돈다.

return은 3이 되어야한다. 왜냐하면 range [1..(N + 1)] 라고 주어졌기 때문에!! N+1 값이 return 되어야하는 것이다.

 

아래가 수정한 코드다.

하나 수정하니까 바로 100점이 나온다 ㅠㅠ

class Solution {
    public int solution(int[] A) {
        int lengthOfA = A.length;
        int answer = lengthOfA+1;

        Arrays.sort(A);
        for(int i=0;i<lengthOfA;i++) {
            if(A[i]!=i+1) {
                answer = i+1;
                break;
            }
        } return answer;
    }
}