코딩에 대한 이해력을 높이기 위한 작성된 글입니다.
여기의 내용은 @NeetCode 유튜버 동영상을 기반으로 작성되었으므로, 문제 발생 시 즉각적으로 삭제하도록 하겠습니다.

LeetCode 217번 문제 (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)이 될 것 입니다.

코딩