[Leet code - 217] Contains Duplicate ✅

문제

주어진 정수 배열에서 중복된 값을 가진 원소가 있다면 true, 없다면 false를 반환하라.

 

 

시간 복잡도

n이 최대 500'000이므로 복잡도가 $O(n \log{n})$이하인 알고리즘을 사용해야 한다.

 

 

해결 계획

간단하게 생각나는 건 두 가지 방법이 있었다

• 정렬 후 순회하여 찾아내는 방법
• 순회하면서 등장한 값을 테이블에 저장하고, 사용하는 방법

두 번째 방법이 아무래도 더 빠른 $O(n)$이므로 해시 테이블을 사용하여 풀이하려 했고,

에지 케이스도 딱히 문제없는 것 같았다!

 

 

구현

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> table;

    for (int data : nums)
    {
        if (table.find(data) != table.end()) return true;

        table.insert(data);
    }

    return false;
}

map이 아닌 set을 사용한 이유는 key가 존재하는지의 여부만 알면 되기 때문에 set을 사용했다.

 

 

되돌아보기

해시를 사용할까 할 때 든 생각인데,

key가 최대 500'000개가 들어올 수 있는 문제라 이 정도면 해시 충돌이 일어나는 것 아닌가? 했었다.

 

하지만 당연하게도 이런 문제쯤은 표준함수답게 이미 처리가 구현이 되어 있었다

STL의 해싱은 내부적으로 체이닝을 사용하여 관리한다고 한다.

 

 

개선 코드

개선? 점은 insert의 반환 값인 $pair<iterator, bool>$를 이용하는 것이다.

두 번째 인자인 bool 값이 새로 삽입되었는지를 알려주기 때문에, 이미 데이터가 있다면 false를 반환하므로 이를 이용해 로직을 합칠 수 있었다.

// Before
if (table.find(data) != table.end()) return true;
else table.insert(data);


// After
if (!(table.insert(data)).second) return true;
// 가독성 버전
if (table.insert(data).second == false) return true;

find 와 insert의 연산 두 가지를 insert 하나로 합친 코드이기 때문에 성능적으로는 확실히 이점이 있다.

하지만 아무래도 find가 가독성이 좋다보니까 호불호가 있을 것 같다!