codility Lesson2 - OddOccurrencesInArray

코드

첫 시도 통과 X
시간복잡도: O(N**2)

// you can use includes, for example:
// #include <algorithm>
#include <set>
// 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)

    // 시간 초과 (big case에서 1초는 아님)
    set<int> S;
    set<int>::iterator iter;
    for(auto a : A) {
    	iter = S.find(a);
    	if(iter != S.end()) {
    		S.erase(a);
		} else {
			S.insert(a);
		}
	}

    return *S.begin();
}

Set에 insert, erase를 반복하며 마지막에 남아있는 값을 반환했는데 시간 초과로 실패했다 ㅠㅠ 다른 사람들 풀이 중에 자바는 HashMap을 사용해서 통과했다는데 언어별로 제한 시간이 달라서 그런 거 같다.

두번째 시도 통과 O
시간복잡도: O(N) or O(N*log(N))

// you can use includes, for example:
// #include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    
    sort(A.begin(), A.end());
    
    for(int i=0;i<A.size();i+=2) {
    	if(A[i] != A[i+1]) return A[i];
    }
    return A.back();
}

정렬을 사용해서 다음 값과 같은지 비교를 해주었다. A[i]를 return 해도 괜찮은 이유는 짝수 개로 짝을 이루었을 때 큰 값은 다음 수와 무조건 같아야 홀수 개의 수가 하나이기 때문이다. 예를들어 3, 3, 4, 5, 5 이런 식으로 나오므로 작은 수를 return 해 줘도 된다. 그리고 A[i+1]에서 터지지 않을까 걱정했는데 A의 index 넘어가는 값을 넣으니 0이 나와서 문제가 없었다.

세번째 시도 통과 O
시간복잡도: O(N) or O(N*log(N))

// you can use includes, for example:
// #include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    
    int answer = 0;
    for(auto a : A) {
        answer ^= a;
    }
    return answer;
}

XOR을 사용해서 문제를 해결했다. XOR은 같은 수면 0이 나오므로 짝이 있는 수들은 다 0이 되므로 마지막에 남아있는 수가 짝이 없는 수이다.

풀이 및 소감

비슷한 문제를 푼 적이 있는데 좀 헷갈려서 풀이를 봤다 ㅠㅠ 슬슬 자야해서 답을 봤는데 다음에는 답을 안 보고 풀어봐야겠다.

---

참고 사이트

• [알고리즘] codility OddOccurrencesInArray 문제 - hojak99님 블로그