[Codility] OddOccurrencesInArray (C++)

4552 단어 codilitycodility

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

배열에서 짝이 없는 값을 찾는 문제이다.
처음에 map 자료구조로 접근했는데 시간복잡도 초과가 떴다.
줄이고 줄여서 O(N) or O(NlogN)까지 줄였는데 마지막 케이스에 걸렸다.

다른 방법을 생각했는데, 간단한 방법이 배열을 sort한 뒤에 두개씩 검사하면 되는 것이다.
바꾸니 문제는 해결됐다.

전체 코드

// 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)
    int answer = 0;
    sort(A.begin(), A.end());

    for(int i = 0; i < A.size(); i+=2){
        if(i == A.size() - 1) {
            answer = A[i];
            break;
        }
        if(A[i] != A[i+1]) {
            answer = A[i];
            break;
        }
    }
    return answer;
}

좋은 웹페이지 즐겨찾기