(Array, Easy) Contains Duplicate

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

Arrays.sort로 오름차순 정렬하고 앞(적은 인덱스)에서부터 순회하다가 Duplicate인 것을 만나는 순간 종료하는 것은 어떨까?

java 8버전 기준 primitive type인 경우 Dual-Pivot QuickSort 쓴다고 알고있는데 평균 O(n log n)이지만 최악 O(n^2) 까지 나올 수 있다. 배보다 배꼽이 더 크다.

그렇다면 그냥 O(n) 순회하면서 맵이나 셋에 넣어놓고 contains인 경우 바로 쳐내는게 제일 빠를 것이다.

import java.util.*;
class Solution {
    public boolean containsDuplicate(int[] nums) {
        
        Set<Integer> set = new HashSet<>();

        for (int n : nums) {
            if (set.contains(n)) return true;
            set.add(n);
        }

        return false;
    }
}

결과는 10 ms / 58.10 MB로 런타임기준 Beats 88.40%가 나온다.
그럼 이것보다 빠른 11.60%는 무엇이란 말인가?

Solutions 코드를 참고해 보니 set의 add 메서드 반환값이 boolean인 것을 활용한다.

contains로 체크하는 경우 일단 넣어두고(add) 다음 순회에 참고할 수 있겠지만, add시 false를 뱉는다면 해당 루프 안에서 바로 중복이 발생했음을 알 수 있기 때문에 상대적으로 조금 더 빠른 결과를 보이는 것 같다.

기본적으로 제공되는 인터페이스를 잘 숙지하자는 교훈을 남긴다.

import java.util.*;
class Solution {
    public boolean containsDuplicate(int[] nums) {

        Set<Integer> set = new HashSet<>();
        for (int n : nums){
            if (!set.add(n)) return true;
        }
        return false;
    }
}