[LeetCode] 217. Contains Duplicate

문제

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.

217. Contains Duplicate는 주어진 배열에서 중복되는 원소가 존재하는지 판단하는 문제다.

BCR(Best Conceivable Runtime)

중복되는 원소가 있는지 확인하려면 배열의 모든 원소를 한 번씩은 확인해야 하므로, BCR은 배열의 길이가 $N$이라고 할 때 $O(N)$이다.

풀이 1

첫 번째로 생각할 수 있는 방법은 완전 탐색이다. 배열을 선형 탐색하면서 nums[i]와 동일한 원소가 배열에 존재하는지 탐색하는 방법이다.

import java.util.*;

class Solution {
    public boolean containsDuplicate(int[] nums) {
    	if (nums.length <= 1) return false;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i != j && nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

nums[i]마다 배열 전체를 탐색하고 있으니 시간 복잡도는 $O(N^2)$, 공간 복잡도는 $O(1)$이다.

풀이 2

풀이 1은 nums[i]마다 중복되는 원소를 탐색하는 곳에서 병목 현상이 발생한다. 만약 주어진 nums를 수정해도 된다고 할때, 배열을 정렬하여 중복되는 원소는 서로 붙어있게 한다면 해당 과정에 대한 시간 복잡도를 줄일 수 있다.

import java.util.*;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length <= 1) return false;
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) return true;
        }
        return false;
    }
}

자바의 Arrays.sort()는 퀵 정렬을 수정한 이중-피봇 퀵정렬(Dual-Pivot Quick Sort)을 사용하기 때문에 평균적인 시간 복잡도는 $O(NlogN)$, 최악의 경우 $O(N^2)$이다. 정렬을 수행한 후 중복되는 원소를 탐색하는 과정은 선형 탐색인 $O(N$)이기 때문에 전체적인 시간 복잡도는 정렬에 의존한다.

풀이 3

$O(N)$의 추가적인 공간을 사용한다면 시간 복잡도를 $O(N)$으로 만들 수 있다. 해쉬 테이블을 이용하여 탐색했던 원소를 기록해둔다면, 현재 탐색 중인 nums[i]의 탐색 여부를 $O(1)$에 수행할 수 있다.

import java.util.*;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length <= 1) return false;
        Set<Integer> set = new HashSet<>();
        for (int num: nums) {
            if (set.contains(num)) return true;
            set.add(num);
        }        
        return false;
    }
}