Codility Lesson 04 - MissingInteger( JAVA )

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

MissingInteger coding task - Learn to Code - Codility

 

문제

- A는 N개의 정수들로 이루어진 배열이다.

- A 배열에는 없는 0보다큰 최소의 양수값을 반환합니다.

- 예시

A = [ 1, 3, 6, 4, 1, 2 ] -> return 5

A = [ 1, 2, 3 ] -> return 4

A = [ -1, -3 ] -> return 1

 

제한조건

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

N은 1 ~ 100,000 사이의 정수이다.

A의 원소들은 -1,000,000 ~ 1,000,000 사이의 정수이다.

 

풀이

- 제한조건에서 변수들은 정수값으로 지정해도 됨을 알 수 있다.

- 제한조건에서 A는 빈배열이 없음을 알 수 있다.

- A배열을 Arrays.sort()로 오름차순으로 정리하고, 음수는 모두 무시되어도 상관없음을 알 수 있다.

- int answer = 1로 초기화 하고 A배열을 for문으로 순회하며 속해있는 양수값들을 비교한다.

- for문을 순회하며 answer와 같은값이 존재하면, answer += 1을 한다.

- 예상되는 시간복잡도 : O(N) - for문을 모두 순회하는 최악의 경우

 

소스코드

// 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
        int answer = 1;
        Arrays.sort(A);

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

        return answer;
    }
}