[배열,해시테이블,정렬] LeetCode 217번 문제 학습

 

문제 설명

Contains Duplicate는 정수 배열 nums에서 중복 숫자가 있는지 확인하는 문제임. 중복 있으면 true, 없으면 false를 리턴하면 됨. 예를 들어, [1,2,3,1]은 1이 두 번 나와서 true, [1,2,3,4]는 중복 없어서 false임. 배열 길이는 0 이상이고, 시간복잡도 O(n log n) 이하나 O(n)으로 푸는 게 좋음.

푼 과정

두 가지 방법으로 풀었음.

 

첫 번째는 정렬 방식. sort.Ints로 배열을 오름차순 정렬하고, 루프 돌면서 nums[i]랑 nums[i-1] 비교해서 같으면 true. 중복 없으면 false.

 

두 번째는 해시셋 방식. map[int]bool 만들어서 숫자 하나씩 보면서 이미 맵에 있으면 true, 없으면 맵에 넣음. 끝까지 중복 없으면 false.

 

이중 루프는 O(n²)이라 비효율적이라 뺌

 

---

알고리즘 분석

정렬 방식은 퀵소트 기반 sort.Ints 써서 O(n log n) 걸림.

인접 비교는 O(n)이라 총 시간 O(n log n).

공간은 제자리 정렬이라 O(1).

해시셋 방식은 맵에 숫자 저장/체크하는데 O(1),

배열 한 번 순회해서 총 시간 O(n).

공간은 맵 때문에 O(n).

 

해시셋이 시간 더 빠르고 직관적, 정렬은 공간 덜 쓰는 대신 시간 느림.

package main

import (
	"os"
	"sort"
	"fmt"
)

// Solved - 1
func containsDuplicate_1(nums []int) bool {
	sort.Ints(nums)

	for i := 1; i < len(nums); i++ {
		if nums[i] == nums[i - 1] {
			return true
		}
	}

	return false
}

// Solved - 2
func containsDuplicate_2(nums []int) bool {
	hash := make(map[int]bool)

	for _, v := range nums {
		if hash[v] == true {
			return true
		}

		hash[v] = true
	}

	return false
}