Codility : Lesson 2 (Array) - OddOccurrencesInArray

안녕하세요~~

디벨롭퍼입니다~~~

 

오늘은 Lesson2 (Array)  : OddOccurrencesInArray 문제를 풀어보았습니다.

 

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

OddOccurrencesInArray coding task - Learn to Code - Codility

***********************************************************************

풀어보실 분들을 위해서 링크 걸어두었습니다.

***********************************************************************

 

주어진 문제는 아래와 같습니다.

 

OddOccurrencesInArray

 

OddOccurrencesInArray coding task - Learn to Code - Codility

최대 1,000,000 개의 배열 원소가 존재하며

원소는 1...10억의 수로 구성되어있습니다.

배열의 원소 중 홀수 개인 원소의 값을 리턴하는 함수를 짜야하는 문제였습니다.

 

문제를 처음보고 생각을 한 건 map을 사용하면 되겠다라고 생각하여

아래와 같이 작성을 했었어요.

 

// you can use includes, for example:
// #include <algorithm>
#include <map>
// 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;
    std::map<int, int> map;
    for(std::vector<int>::iterator iter = A.begin(); iter != A.end(); ++iter)
    {
        if(map.find(*iter) == map.end())
        {
            map.insert({*iter, 1});
        }
        else
        {
            map[*iter]++;
        }
    }

    for(std::map<int, int>::iterator iter = map.begin(); iter != map.end(); ++iter)
    {
        if((*iter).second & 1) 
        {
            answer = (*iter).first;
        }
    }
    return answer;
}

 

그런데 왠 걸.. timeout이 나버렸지 뭐에요

조금은 당황했지만 왜 그런지 구글링을 해보니

저는 map이 hash 기반의 STL인 줄 알았는데 그게 아니였더라구요

 

map은 RB Tree기반 동작, unorderd_map이 hash 기반 동작이였었습니다.

 

그래서 unordered map으로 수정하니 통과를 하더군요.

아래의 코드는 map을 unordered_map으로 바꾸었습니다.

 

// you can use includes, for example:
// #include <algorithm>
#include <unordered_map>
// 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;
    std::unordered_map<int, int> map;
    for(std::vector<int>::iterator iter = A.begin(); iter != A.end(); ++iter)
    {
        if(map.find(*iter) == map.end())
        {
            map.insert({*iter, 1});
        }
        else
        {
            map[*iter]++;
        }
    }

    for(std::unordered_map<int, int>::iterator iter = map.begin(); iter != map.end(); ++iter)
    {
        if((*iter).second & 1) 
        {
            answer = (*iter).first;
        }
    }
    return answer;
}

문제는 이렇게 해결했지만 

map 과 unordered_map의 차이를 확실히 알아야 할 것 같네요.

다음 포스팅엔 map과 unordered_map의 차이를 설명해보도록 하겠습니다.

그럼 이만~~