Lesson2 - OddOccurrencesInArray - with unordered_map

 

문제

input : 홀수 크기의 배열 A

output : pair를 갖지 못한 값

배열 A의 각각의 값은 index 순서대로 같은 값을 가지면 pair를 맺는다. 그중 pair를 맺지 못한 배열 안의 값을 구하라.

 

풀이

시간복잡도는 N크기만큼 for문을 돌고 for문안에 unordered_map의 find작업만 해서 O(N) * O(1) => O(N)으로 예상한다.

codility analysis

• A의 값을 모두 조사하기 위해서 for문을 호출한다.
• A[i] 의 map의 key값으로 설정하고, key값으로 임의로 지정한 boolean value값이 있는지 찾는다. -> O(1)
• key값이 나온 적이 없는 경우 OddOccurrences의 후보.
• key값이 나온적이 있는 경우 pair를 맺고 map에서 제외시킨다.
• 문제에서 하나를 제외하고 모든 값들이 pair를 맺기 때문에 map의 가장 첫 번째 key값이 답이다.

 

코드

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<int,bool> number_map;
int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    
    int answer =0;

    for(int i =0; i<A.size(); i++){
        int key = A[i];
        //key값이 나온적이 없을 경우
        if(number_map.find(key) == number_map.end()){
            number_map.insert({key, true});
        }else{
            number_map.erase(key);
        }
    }
    
    auto it = number_map.begin();
    answer = it->first;

    return answer;

}

★ pair를 이루는 문제가 나올때는 unordered_map을 활용해서 시간 복잡도를 줄이자.

★ 문자열을 key로 사용할 경우 문자열이 길어지면 unordered_map말고 그냥 map의 성능이 좋다고 한다.

by https://gracefulprograming.tistory.com/3

[C++] map vs hash_map(unordered_map)