217. Contains Duplicate - C

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Answer 1: Time Limit Exceeded (18 / 18 test cases passed, but took too long.)

bool containsDuplicate(int* nums, int numsSize){
    int i, j;
    
    for(i=0;i<numsSize;i++)
    {
        for(j=i+1;j<numsSize;j++)
        {
            if(nums[i] == nums[j])
            {
                return true;
            }
        }
    }
    
    return false;
}

역시 맨처음 떠올린 건 이중 for문^^ 써서 중복 찾기였음
당연히 모든 케이스가 잘 동작하지만 매우 비효율적이라는 점..

본격적으로 효율을 어떻게 높일까 하다가 두가지가 떠올랐음
하나는 재귀를 사용하는 것 -> 시도했지만 너무 복잡해질 것 같아서 포기
하나는 정렬 후 중복 찾기 -> 효율이 좋은 quick sort 를 사용하려했지만 코드가 드러워서 포기
해쉬 쓰는 것도 생각해봤는데 c 로는 넘 드러워서 넘김

분명 논리로는 간단한데 c 는 왜이리 더러운건지.. solution 을 찾아봄
c solution 들은 qsort 사용 후 comp 함수를 만드는게 가장 베스트 같은데 qsort 를 첨본다
quicksort 가 아닐까 생각..

도저히 안되겠어서 c++로 바꿨다ㅠ

Answer 2: Accepted (Runtime: 48 ms / Memory Usage: 15.9 MB)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // 0개나 1개면 중복일 수 없으니 0
        if(nums.size() < 2)
        {
            return false;
        }
        
        // sort 함수로 정렬 (시작~마지막)
        sort(nums.begin(), nums.end());
        
        // i+1까지 비교하니까 nums.size()-1까지
        for(int i=0;i<nums.size()-1;i++)
        {
            if(nums[i] == nums[i+1])
            {
                return true;
            }
        }
        
        return false;
    }
};

아까 생각한 방식의 두번째인 정렬 후 비교를 수행 !!
sort 함수야 고마워~

• hash 의 역할을 하는 c++ 의 unordered_map 도 이용해볼것~
• 찾아보니 파이썬이 가장 간단한 것 같다.. 빨리 파이썬으로 갈아타야 정신적으로도 좋을듯;