Lesson 4(Counting Elements) - MissingInteger

 문제

This is a demo task.

Write a function:

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

that, given an array A of N integers, returns the smallest positive integer (greater than 0)
that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

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

주어진 정수형 배열 A에서 양의 정수 중 누락된 최소값을 찾는  문제이다.

 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        int [] chkArr = new int[1000001];
        int maxCnt=0;
        int cnt=0;
        
        for(int i=0; i<A.length; i++){
            if(A[i] > 0){
                chkArr[A[i]]++;
                cnt++;
            }
        }
        
        if(A.length == 1){
        	if(chkArr[1] == 1) return 2;
        	else return 1;
        }

        for(int j=1; j<=cnt; j++){
            if(chkArr[j] == 0){
                return j;
            }
            maxCnt = j;
        }
        
        return maxCnt+1;
    }
}

임의의 정수형 배열을 만들어 주어진 배열 A에서 양수값에 해당하는 인덱스에 카운팅하여 최소값을 찾습니다.

테스트한 샘플은 아래에 있습니다.

int [] A = {1,2,3};  //배열 내에 누락된 값이 없을 경우 최대값 +1
int [] B = {1};       //배열 내에 누락된 값이 없을 경우 최대값 +1 AND 배열크기가 1
int [] C = {2};      //배열 내에 누락된 값이 있을 경우 최대값 +1 AND 배열크기가 1
int [] D = {-1};    //음수값 처리 AND 배열크기가 1
int [] E = {1,1,2,3}; //중복된 값처리 처리

각 결과값은 다음과 같습니다.
A : 4
B : 2
C : 1
D : 1
E : 4

 결과

주소 : app.codility.com/demo/results/trainingVAJNJA-JT3/

제출결과 1

 

제출결과2

문제 난이도가 미디엄으로 조금 어려워졌습니다.
문제 자체가 어렵다기보단 예외사항을 조금 생각해 보고 작성하면 큰 어려움 없이 풀 수 있을 문제라고 생각됩니다.