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

문제 설명

Contains Duplicate II는 정수 배열 nums와 정수 k가 주어졌을 때, 중복된 숫자가 있고 그 숫자들의 인덱스 차이가 k 이하인지 확인하는 문제임. nums[i] == nums[j]이고 |i - j| <= k면 true, 아니면 false를 리턴하면 됨. 예를 들어, nums = [1,2,3,1], k = 3이면 인덱스 0과 3에서 1이 중복이고 |3-0| = 3 <= k라 true. nums = [1,2,3,1,2,3], k = 2면 중복 있어도 인덱스 차이가 k 초과라 false.

푼 과정

해시맵으로 풀었음. map[int]int 만들어서 숫자와 그 인덱스를 저장함. 배열 순회하면서 숫자 v가 맵에 이미 있으면, 현재 인덱스 i와 이전 인덱스 val의 차이 i - val이 k 이하면 true 리턴. 아니면 맵에 v의 인덱스를 i로 갱신. 끝까지 중복 없거나 조건 안 맞으면 false. 코드 간단하고 문제 요구사항 딱 맞췄음.

---

알고리즘 분석

해시맵 썼음. 맵에 숫자 저장/체크는 O(1), 배열 한 번 순회하니까 총 시간 O(n). 공간은 맵 때문에 O(n). 정렬 방식은 인덱스 정보 잃어서 부적합했는데, 해시맵으로 간 거 최적 선택임. 브루트 포스는 O(n²)이라 느리고, 해시맵이 시간/공간 균형 잘 맞춤.

 

package main

import (
	"os"
	"fmt"
)

func containsNearbyDuplicate(nums []int, k int) bool {
	maps := make(map[package main

import (
	"os"
	"fmt"
)

func containsNearbyDuplicate(nums []int, k int) bool {
	maps := make(map[int]int)
	for i, v := range nums {
		if val, exists := maps[v]; exists && i - val <= k {
			return true
		}
		maps[v] = i
	}

	return false
}

func main() {
	inp1 := []int{1, 2, 3, 1}
	inp2 := []int{1, 0, 1, 1}
	inp3 := []int{1,2,3,1,2,3}

	fmt.Fprintln(os.Stdout, containsNearbyDuplicate(inp1, 3))
	fmt.Fprintln(os.Stdout, containsNearbyDuplicate(inp2, 1))
	fmt.Fprintln(os.Stdout, containsNearbyDuplicate(inp3, 2))
}