[코딩연습] Contains Duplicate 중복 포함 여부

LeetCode 문제 중 난이도 Easy인 Contains Duplicate이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

정수 배열을 입력값으로 받아 해당 배열이 중복값을 포함하고 있는지 판별하라.

아무 값이나 배열 내에서 두번 이상 나타나는 값이 있다면 true를 리턴하고 모든 요소가 유일하다면 false를 리턴해라.

첫번째 방법은 배열을 정렬한 후 앞뒤 값을 비교하는 것이다. 이전에 포스팅한 Single Number 문제의 첫번째 풀이법과 원리가 같다.

2019/03/16 - [프로그래밍문제풀기] - [코딩연습] Single Number 하나뿐인 숫자 찾기

class Solution {
    public boolean containsDuplicate(int[] nums) {
        
        Arrays.sort(nums);
        
        for(int i=0 ; i<nums.length-1 ; i++){
            //앞뒤 값이 같은게 나오면 true리턴
            if(nums[i] == nums[i+1]) return true;
        }
        
        //for문을 빠져나와 전체 배열을 다 돌때까지 중복이 없으면 false리턴
        return false;
    }
}

정렬하는데 드는 시간 O(nlogn), 탐색하는데 드는 시간 O(n)으로 시간복잡도는 O(nlogn)이고 추가적인 메모리 사용이 없으므로 공간복잡도는 O(1)이다.

두번째 방법은 Set 자료구조를 이용하는 것이다. Set은 중복된 데이터를 허용하지 않는 집합이다. 만약 nums에 중복된 값이 있다면 nums의 길이와 numset의 사이즈가 다를 것이다.

ex) nums = [3,7,7,8,6] 일 경우 nums.length=5, numSet.size()=4

class Solution {
    public boolean containsDuplicate(int[] nums) {
        
        Set<Integer> numSet = new HashSet<>();
        
        for(int i=0 ; i<nums.length ; i++){
            numSet.add(nums[i]);
        }
        
        //배열의 길이와 배열의 요소를 모아놓은 집합의 크기가 다르면 true, 같으면 false 리턴
        return nums.length != numSet.size();
    }
}

이 방법은 배열을 한번만 탐색하므로 시간복잡도는 O(n)이지만 numSet이라는 추가적인 공간을 사용하므로 공간복잡도는 O(n)이다.

문제 출처 - https://leetcode.com/problems/contains-duplicate/