[Codility] OddOccurrencesInArray (C++)
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;
}
Author And Source
이 문제에 관하여([Codility] OddOccurrencesInArray (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@khc41/Codility-OddOccurrencesInArray-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)