[171116][Codility](C#)Missing Integer

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

 

문제>

주어진 배열 A에서 발생하지않은 0보다 큰 양의 정수를 반환하라.

 

해결방법.

* A를 정렬. 

* HashSet로 중복제거.(퍼포먼스를 위함)

* A를 리스트로 변환 후 1보다 작은 수들 제거.

* 만약 A의 데이터 수가 1보다 작거나 1이 없다면 1을 반환.

- 아니라면 순차적으로 누락값(A[i + 1]과 A[i]의 차가 1이상)을 찾는다.

- 누락값이 없다면 A의 최종값에 +1을 해서 반환.

 

using System;
using System.Collections.Generic;

class Solution
{
    public int solution(int[] A)
    {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        Array.Sort(A);
        HashSet<int> deduplication = new HashSet<int>(A);
        List<int> _A = new List<int>(deduplication); 
        _A.RemoveAll(obj => obj < 1);

        if (_A.Count < 1 || _A[0] > 1)
            return 1;
        else
        {
            for (int i = 0; i < _A.Count - 1; i++)
            {
                if (_A[i + 1] - _A[i] > 1)
                    return _A[i] + 1;
            }
            return _A[_A.Count - 1] + 1;
        }
    }
}

 

 

 

 

 

17.11.16.(0200)

 

회고 : HashSet를 처음 써봤다. for로 중복제거 했더니 퍼포먼스가 엄청 안나와서 삽질한 문제.