LeetCode 217. Contains Duplicate

알고리즘 면접 대비용으로 작성하는 시리즈! (Blind75를 따라감)

목표:
두가지 이상의 풀이방법을 구현하고 설명하기
시간/공간 복잡도를 나타내기
왜 이 풀이가 저 풀이보다 성능이 나은지 논리적으로 설명하기
면접질문에 대답한다고 생각하고, 핵심을 설명하되 말을 너무 길게 하지 않기 (개인적으로는 세 문장이 적절하다고 생각)
분명하고 적절한 용어를 사용해서 설명하기

---

질문:
LeetCode 문제
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.

Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

 

 

 

Solution 1

Brute force

var containsDuplicate = function(nums) {
	for (let i = 0; i<nums.length-1; i++){
		for (let j = i+1; j<nums.length; j++){
			if (nums[i] === nums[j])
				return true;
		}
	}

	return false;
};

· 배열의 특정 i번째 원소를 피봇으로 잡고, 이후의 원소들을 순회하면서 nums[i]와 nums[j]가 같은지 찾는다.

· 단, nums의 크기가 커질 경우 시간이 초과된다.

· 시간복잡도/공간복잡도: O(n^2)/O(1)
최대 두 번의 loop문을 돌 수있기 때문에 시간복잡도는 O(n^2)이며, i와 j의 값만 메모리에 저장하기 때문에 공간복잡도는 O(1)이다.

 

 

 

Solution2

sort

var containsDuplicate = function(nums) {
  nums.sort();
  for (let i = 1; i<nums.length; i++){
    if (nums[i] === nums[i-1])
      return true;
  }

  return false;
};

· nums를 먼저 정렬한 뒤, 인접한 원소끼리 비교한다.

· 시간복잡도/공간복잡도: O(n logn)/O(1)
sort의 시간복잡도인 O(n logn) + 반복문의 시간복잡도 O(n) = O(n logn), i 값만 메모리에 저장하기 때문에 공간복잡도는 O(1)이다.

sort의 시간복잡도에 대해서는 이 글에도 작성했다.

 

 

 

Solution3

Hashmap

var containsDuplicate = function(nums) {
    let hash = {};
    for (let i = 0; i<nums.length; i++){
        if (hash[nums[i]])
            return true;

        hash[nums[i]] = true;
    }
    
    return false;
};

 

· Hashmap을 선언하여, nums를 순회하며 hashmap에 해당 원소가 있는지 확인하고, 있는 경우 true를 반환, 아닌 경우에는 hashmap에 해당 원소를 추가한다.

· key만 존재해도 되는데 value까지 넣게 되는 상황이 불필요해 보일 수 있다.

 

· 시간복잡도/공간복잡도: O(n)/O(n)
반복문 1회 / 최대 nums.length길이의 hashmap을 가질 수 있음

 

 

 

 

Solution4

Set 사용

var containsDuplicate = function(nums) {
	let myset = new Set();

	for (let i = 0; i<nums.length; i++){
		if (myset.has(nums[i]))
			return true;
		myset.add(nums[i]);
	}

	return false;
};

· Solution3에서, value가 꼭 필요하지 않다는 점에서 착안하여 set을 사용할 수 있다.

· 시간복잡도 / 공간복잡도: O(n) / O(n)

 

 

Solution5

Set의 속성을 사용

var containsDuplicate = function(nums) {
    return new Set(nums).size !== nums.length;
};

 

· nums를 set으로 만들면 중복되는 값들이 사라지며 set의 크기가 변경될 수 있다.

 

· 시간복잡도/공간복잡도: O(n)/O(n)
nums를 set으로 변환하는 시간 / nums를 새로운 set으로 만드는 공간