Lesson 2. Arrays - OddOccurrencesInArray #2 (속도 개선)

1. 속도 개선 아이디어

정답을 제외하고, 모든 요소는 짝수로 있다. 즉, 최소 2개 이상이다.

vector A의 요소들을 정렬시키면, 중복되는 요소들이 나란히 붙어 있을 것이다.

그리고 이들은 짝수개이므로, +2씩 점프하면서 확인할 수 있다.

 

2. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A)
{
    //정렬
    sort(A.begin(), A.end());
    
    //검색
    for(size_t i = 0; i < A.size(); i += 2)
    {
    	//정렬했으므로, 같은 값이 나란히 붙어 있다.
        //만약 앞, 뒤 값이 다르다면, 정답을 찾은 것이다.
        if(A[i] != A[i+1]) return A[i];
    }

    return 0;
}

 

 

3. 결과