[Codility] Lesson 4 : MissingInteger - JAVA

문제

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

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에서 배열 A의 N의 정수를 가지고 있으며, N의 범위는 1 ~ 100,000이다.
배열 A에는 정수 -1,000,000부터 1,000,000까지 숫자를 요소로 가질 수 있다.

N개의 정수로 이루어진 배열 A에서 존재하지 않는 양의 정수(0보다 큼)를 찾아 반환한다.

예를 들어
        A = [1, 3, 6, 4, 1, 2] 이면 숫자 배열 안에 존재하지 않는 가장 작은 양의 정수는 5이다.
        A = [1, 2, 3] 이면 숫자 배열 안에 존재하지 않는 가장 작은 양의 정수는 4이다.
        A = [-1,- 3] 이면 숫자 배열 안에 존재하지 않는 가장 작은 양의 정수는 1이다.

이렇게 배열 A에 존재하지 않는 가장 작은 양의 정수를 결과로 반환해주면 된다.

 

풀이 - 1

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int before = 0;
        for(int subA : A) {
            if(subA <= before) continue;
            if(subA > (before+1)) return before+1;
            before = subA;
        }
        return before+1;
    }
}

 

'풀이 - 1'에 대한 회고

 

Time spent는 22min이지만 Score는 100%!

먼저 배열 A를 오름차순으로 정렬해준 뒤 반복문을 통해 비교한다.

만약 반복문을 통해 배열 A에서 꺼낸 값이 이전에 꺼낸 값보다 2 이상 크면

이전 값과 배열 A에서 꺼낸 값 사이의 숫자(양의 정수)가 누락되었다는 것!

그렇게 해서 '풀이 - 1'처럼 풀었다.

 

 

다행히 정확도와 퍼포먼스 모두 100%를 받았다.

 

 

그리고 시간복잡도!

나의 풀이는 시간복잡도가 O(n) 이상일 것이라 예상하면서 풀었는데 역시나!

O(n)이 맞다!

 

이제 다른 방법을 조금 더 생각해보고,

다른 사람들은 어떻게 풀었는지 확인해봐야겠다.

 

다른 사람의 풀이

import java.util.HashSet;
class Solution {
    public int solution(int[] A) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int subA : A) {
            set.add(subA);
        }
        for(int i = 1; i<1000001; i++) {
            if(!set.contains(i)) return i;
        }
        return 1;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

다른 사람이 푼 문제의 정확도, 퍼포먼스, 시간복잡도는 '풀이 - 1'과 동일하기 때문에 별도로 첨부하지 않았다.

나와 비슷하게 문제를 푼 사람도 있지만 boolean 배열을 이용한 사람도 있었다.

그리고 코드와 같이 HashSet을 이용해서 풀이한 사람도 있다.

 

HashSet에는 값이 중복될 수 없기 때문에 Missing Integer를 찾을 때 시간을 단축할 수 있다.

다만 배열 A를 Set으로 변환하기 위해 이미 시간복잡도가 O(n)이 된다.

그렇기 때문에 Missing Integer를 찾는 과정이 많이 단축되었다고 보기는 힘들 것 같다.

 

그래도 HashSet을 활용한 방법도 있다는거~!