Contains Duplicate

problem

주어진 배열이 중복된 원소를 가지고 있는지 검사하는 문제입니다.

https://leetcode.com/problems/contains-duplicate/

solution

풀이1, 정렬을 이용

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        bool result = false;
        
        sort(nums.begin(), nums.end());
        
        for(int i=0; i<nums.size()-1; i++){
            
            if(nums[i] == nums[i+1]) {
                result = true;
                break;
            } 
        }
        return result;
    } 
   
};

풀이 2, set을 이용

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> s;
        
        for(int i=0; i<nums.size();i++){
            pair<set<int>::iterator, bool> tmp = s.insert(nums[i]);
            if(tmp.second == false) return true;
        }
        return false;
    }
};

후기

처음에는 정렬하는 것도 생각해보았지만, 퀵정렬을 해도 O(n)은 안되니까 set으로 먼저 구현했다.

그러나 의외로 sort보다 나쁜 점수가 나오고 말았다.

알고리즘의 sort는 퀵정렬은 O(nlogn)으로 알고 있었는데, 속도가 느린것이 이해가 가지 않았다.

생각해보면, set은 이진트리로 구성되어있고, map은 hash의 자료구조를 가지므로, 집합이나 hash 테이블에 접근하면서, 추가적인 작업이 항상 O(1)일리가 없었기 때문에,

집합에 원소를 다 넣는, 두번째 코드의 실행 시간이 O(N)이 아닐 수 있을 것 같았습니다.