Codility Lesson 03 - PermMissingElem( JAVA )

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

PermMissingElem coding task - Learn to Code - Codility

문제

- A 배열에는 모두 다른 정수가 주어진다. ( 범위 : 1 ~ N+1 )

- 놓친( missing ) 원소를 찾는 것이 목표

- 예시 : [ 2, 3, 1, 5 ] / 답안 : 4

 

제한조건

• 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)].

N은 0 ~ 100,000 범위의 수이다.

A 배열의 원소들은 모두 구분된다( 중복되는 수가 없다 )

A 배열의 원소들은 1 ~ N+1 범위 안의 수이다.

 

풀이

- 주어진 배열을 정렬하여( Arrays.sort() ) 하나씩 비교하며 찾는 방법을 사용한다.

- 중간의 원소가 빠진 경우 / 끝에 원소가 빠진 경우를 나눠서 분기해주어야 한다.

- 비어있는 배열의 경우? 1 return

- 변수 int answer=1로 초기화 후 A배열 안의 원소와 비교하며 확인( 같은게 존재하는 경우 answer++ )

 

소스코드

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8

        if( A.length == 0 ){
            return 1;
        }

        Arrays.sort(A);
        int answer = 1;

        for( int i:A ){
            if( answer == i ){
                answer++;
            }else{
                break;
            }
        }

        return answer;
    }
}