[ leetcode 문제풀이 ] Contains Duplicate

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

Contains Duplicate - LeetCode

(Contains Duplicate 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Contains Duplicate 문제 설명 > 

 

Contains Duplicate 문제는 다음과 같다.

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

주어진 정수 배열 nums에 대해 중복된 원소가 있으면 true, 없으면(모든 원소가 서로 다르면) false를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다. 

 

주어진 제한 조건은 1 ≤nums.length ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9 이다.

 

 

 

---

< Contains Duplicate 문제 접근(1) > 

 

만약 중복된 숫자가 있다면, nums 배열을 정렬했을 때, 인접한 두 숫자가 같은 경우가 반드시 존재할 것이다. 이를 탐색하는 것을 코드로 나타내면 다음과 같다. (Cpp 사용)

 

#include <algorithm>
using namespace std;

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

 

<algorithm> 헤더파일에서 지원하는 sort함수는 quick sort를 기반으로 구현되어 있어 평균적으로 O(n log n)의 시간복잡도를 갖는다. 위 코드의 경우 처음 sort함수가 전체 시간복잡도를 좌우하므로 총 O(n log n) 복잡도라고 할 수 있다.

 

 

 

---

< Contains Duplicate 문제 접근(2) >

 

또 다른 방법으로는 hash table을 이용하는 방법이 있다. nums의 원소를 훑으며 nums[i]를 key로 갖는 key, value 쌍이 있는지를 확인하는 것이다. 이를 코드로 나타내면 다음과 같다. (Cpp 사용)

 

#include <unordered_map>
using namespace std;

bool containsDuplicate(vector<int>& nums){
    unordered_map<int, int> memory;
    
    for(int i=0;i<nums.size();i++){
        if(memory[nums[i]])
            return true;
        memory[nums[i]]++;
    }
    return false;
}

 

if문 내에서 memory[nums[i]]를 하게 되면 
1) nums[i]를 key로 갖는 key, value 쌍이 없는 경우

  → nums[i] key로 갖고 value는 자동으로 0으로 초기화되는 key, value 쌍이 형성된다.

2) nums[i]를 key로 갖는 key, value 쌍이 있는 경우

  →nums[i]의 value를 불러온다.

 

따라서, 중복되지 않은 숫자(nums[i])에 대해서는 if문은 false처리 되고, 그 후 memory[nums[i]]++에 의해 key nums[i]에 대한 value가 1로 증가한다. 이 연산을 통해 탐색 중 nums[i]를 key로 갖는 key, value 쌍이 존재하는 경우(memory[nums[i]] == 1) if문이 true 처리 되고 true를 리턴하게 된다. 전체 영역에 대해 탐색하였으나 이와 같은 경우가 없다면 false를 리턴하게 된다.

 

nums의 index를 순회하는 과정 O(n) * hash table의 원소 찾기 O(1)으로 총 O(n)의 시간복잡도를 갖는다.

 

 

여기까지만 보면 hash table을 사용한 경우가 더 빨라야 하지만, 실제 출력 결과 runtime은

정렬: 76 ms, hash table: 96 ms로 정렬이 좀 더 빨랐다.

 

코드의 구조는 비슷하였기에 이 속도의 차이가 어디서 발생하였는지 잘 모르겠다.