[LeetCode] Contains Duplicate

문제

풀이

1. Brute Force 사용 

 

num = [1, 2, 3, 1] 
Brute Force을 사용하게 된다면, 각각의 element들의 대해 비교를 해야하므로 비효율적 일 것 입니다. 이에, Time Complexity 차원에서 O(N^2) 일 것이고, Space Complexity 으로는 O(1) 일 것 입니다. 이러한 접근방법도 충분히 활용 가능하지만, Time Complexity 차원에서 효율적인 방안이 있을 겁니다. 

 

2. Sorting 방법 사용 

 

num = [1 ,2 ,3 ,1] 
num_sorted = [1, 1, 2, 3] 
num 이라는 array에 대하여 sorting을 하게 된다면, num_sorted 이라는 값이 적용 될 것 입니다. 이를 통해 한번만 iterate 해야된다는 장점이 있어, 첫번째 Brute Force 보다 효율적 일 것 입니다. 또한, Sorting을 통하여 첫번째 element에 대하여 adjacent element에 대해 비교하면 될 것이고 또 다른 index로 넘어가서 비교하면 될 것 입니다. 하지만, sorting 이라는 function의 특성 상, Time Complexity는 O(nlogn)이 될 것 이고 Space Complexity는 O(1)이 될 것 입니다. 
너무나 좋은 방법이겠지만, TC 및 SC에 둘 중 하나를 희생하게 된다면, 더욱 더 효과적인 방법이 있습니다. 

 

3. HashSet 

HashSet는 추가적은 메모리가 필요하게 됩니다. 하지만 이는 그 무엇보다 효율적 입니다. 
num = [1,2,3,1] 에 대하여, HashSet을 작성하고 Index 값을 차례대로 넣어서 비교하게 된다면, 중복 값에 대해 파악 할 수 있습니다. HashSet을 만들게 되어, TC 및 SC는 O(N)이 될 것 입니다.

 

코딩