SW/알고리즘

codility : OddOccurrencesInArray : C++ : 문제풀이

얇은생각 2019. 10. 31. 07:30
반응형

코드

// you can use includes, for example:
// #include <algorithm>
#include <algorithm>
using namespace std;

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    sort(A.begin(), A.end());
    
    for(int i=0; i<A.size(); i=i+2){
        if(A[i] != A[i+1]){
            return A[i];
        }
    }
}

 

 

 

실행 결과

TASKS DETAILS : EASY

OddOccurrencesInArray : Find value that occurs in odd number of elements.

Task Score : 100%

Correctness : 100%

Performance : 100%

Detected time complexity : O(N) or O(N*log(N))

 

 

총평

우선 입력 받은 배열을 std 라이브러리를 사용해, 정렬을 해줍니다. 그러면 크기 순대로 정렬이 되기 때문에, 2개씩 짝을 지어 정렬이 될 것입니다. 만약 짝이 안맞는 경우에 한해서는 다음 수와 일치하지 않을 것이라 생각하였습니다. 따라서, 정렬을 한 후, 홀수번째의 수가 다음번 수와 일치하는 지에 대해 여부를 체크하고, 일치하지 않은 경우에는 해당 값을 리턴해주도록 하여 문제를 해결하였습니다.

반응형