Contains Duplicate II
문제
정수 배열 nums와 정수 k가 주어질 때, 배열 내에서 두 개의 다른 인덱스 i와 j에 대해 nums[i] == nums[j]
이며 abs(i - j) <= k
인 경우 true를 반환하라.
접근 방향
map 자료형을 사용해 요소를 키로 갖고 해당 요소를 가르키는 인덱스를 값으로 갖도록 하면 nums 순회시 동일한 요소 있을 경우 해당 요소를 키로 하여 값을 추출한 인덱스를 현재 인덱스와 비교한 뒤 만약 두 값을 차감한 절댓값이 k보다 작을 경우 True를 반환하도록 한다.
나의 풀이
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
# map 자료형 초기화
numMap = {}
# nums 배열 순회
for i in range(len(nums)):
# 만약 numMap에 nums[i]가 키로 존재할 경우
if nums[i] in numMap:
# 이미 존재하고 있는 동일한 요소의 인덱스를 j에 저장
j = numMap[nums[i]]
# 현재 인덱스와 위에서 추출한 j를 차감한 절댓값과 k를 비교하여 k보다 작을 경우
if abs(i - j) <= k:
# True 반환
return True
# 현재 요소를 키로 갖고, 인덱스를 밸류로 갖도록 값을 할당
numMap[nums[i]] = i
return False
다른 사람의 풀이
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
# 중복 비교
# 세트 자료형으로 변경하여 유니크한 값의 길이와 nums의 길이와 동일하다면
# 중복이 없다는 의미이므로 False를 반환
if len(set(nums)) == len(nums):
return False
# map 자료형 할당
dict = {}
# enumerate 함수를 이용하여 인덱스와 배열 요소 순회
for i, value in enumerate(nums):
# 만약 요소가 dict의 키로 존재하면서 해당 인덱스와 현재 인덱스를 차감한 절댓값이 k보다 작다면 True를 반환
if value in dict and abs(i - dict[value]) <= k:
return True
# 인덱스를 값으로 갖고 배열 요소를 키로 갖도록 값 저장
dict[value] = i
return False
기본적인 동작방식은 동일하지만 반복문 순회시 enumerate를 사용하여 인덱스와 배열 요소를 순회하면서 추출한다는 점과 가장 처음에 nums가 가진 배열 요소들의 중복 여부를 set 자료형을 사용해 비교한다는 점이 다르다.