[Codility(코딜리티)] Lesson4. MissingInteger (100%)

Lesson 4 Counting Elements - MissingInteger (100%)

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

MissingInteger coding task - Learn to Code - Codility

---

문제

길이 N의 배열 A가 주어진다

A에 포함되어 있지 않은 가장 작은 양의 정수를 구하는 문제이다

예를들면,

A = [1,3,6,4,1,2] -> A에 없는 가장 작은 양의 정수는 5이다

A = [-1,-3] -> A에 없는 가장 작은 양의 정수는 1이다

A = [1,2,3] -> A에 없는 가장 작은 양의 정수는 4이다 

 

해결

HashSet으로 풀었다

HashSet에 배열 A에서 양의 정수만 넣는다

그리고 1부터 A의 배열길이+1만큼 돌면서,

contain()으로 체크하면서 해당 양의 정수가 없으면 그 값을 출력한다

HashSet의 contain() 함수는 O(1)이므로, 총 O(N)으로 해결할 수 있었다

public class MissingInteger {

    public int solution(int[] A) {
        int result = 1;

        Set<Integer> set = new HashSet<>();
        for (int i : A) if (i>0) set.add(i);

        for (int i=1; i<=set.size()+1; i++) {
            if (!set.contains(i)) {
                result = i;
                break;
            }
        }

        return result;
    }
 }