[ Codility ] - Lesson4 MissingInteger(C++)

문제조건

• 값이 정의된 벡터 A

문제설명

  이번 문제는 예전에 풀었던 OddOccurrencesInArray문제인데 정의된 값들 중에 비어있는 값을 찾아내는 문제로 차이점은 이번 문제는 중복 된 값이 나올 수 있다는 점입니다. 따라서 xor을 사용하지 않는 방법을 채택하면 됩니다.

문제풀이

int solution(vector<int> &A) {
    int com = 1;			// 가장 작은 자연수 정의

    sort(A.begin(), A.end());		// 벡터 A 정렬

    for ( int i =0; i < A.size(); i++ )
    {
        if ( com == A[i] ) { com++; }	// 현재까지 나온 최소값과 비교
    }

    return com;
}

코드설명

  가장 먼저는 com변수를 1을 할당하여 선언해 줍니다. 벡터 A를 한 번 정렬하고, 반복문을 돌려줍니다. 반복문이 돌아갈 동안 com변수와 A[i]가 같으면 com++을 해줍니다. 만약 com변수와 A[i]의 값이 같지 않을 경우엔 그 시점의 com변수가 벡터 A에서 비는 값을 의미하게 됩니다.(같은 수가 중복되어 나오는 경우 제외) 그리고, 값을 1로 뒀기 때문에 예시에서 -1, -3을 던져주면 자동으로 1을 반환해 줄 수 있습니다. 그렇게 비어있는 값을 찾아 반환해주면서 프로그램을 종료합니다.

결과사진