Contains Duplicate
정수 배열 nums가 주어집니다. 어떤 값이 배열에 두 번 이상 나타나면 true를 반환하고, 모든 값이 서로 다르면 false를 반환하세요.
함수
- numsinteger-array
- 확인할 정수
- 반환값boolean
- 어떤 값이 두 번 이상 나타나면 true, 그렇지 않으면 false
제약 조건
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
예제
- 입력
- nums = [3, 1, 4, 1, 5]
- 출력
- true
- 설명
- 값
1은 인덱스 1과 인덱스 3에 다시 나타나므로 답은true입니다.
- 입력
- nums = [2, 7, 1, 8]
- 출력
- false
- 설명
2,7,1,8은 서로 다른 네 개의 값이므로 반복되는 값이 없습니다.
- 입력
- nums = [-4, 4, 0]
- 출력
- false
- 설명
-4와4는 절댓값이 같지만 서로 다른 수이고,0은 한 번만 나타나므로 답은false입니다.
제출 시 숨은 테스트 +17개
후속 질문
항상 배열 전체를 읽는 대신, 처음으로 반복되는 값을 만나자마자 멈출 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 값을 서로 비교하는 방식은 작동하지만,
10^4개의 값에 대해서는 약5 × 10^7번의 비교가 필요합니다. 이미 확인한 값에 대해 무엇을 기억해 둘 수 있을까요?반복이란 현재 값이 이전에 이미 만난 값이라는 뜻입니다. 해시 집합은 평균적으로 상수 시간에 "이 값을 이미 만난 적이 있나요?"라는 질문에 답합니다.
빈 집합으로 배열을 한 번 순회합니다. 각 값에 대해 이미 집합에 있으면
true를 반환하고, 그렇지 않으면 값을 추가합니다. 반복문이 끝나면 모든 값이 서로 달랐다는 뜻입니다.
풀이
반복은 이전에 본 적 있는 값이며, 핵심은 “이 값을 본 적이 있나?”라는 질문에 빠르게 답하는 것입니다. 모든 쌍을 비교하면 답을 얻을 수 있지만, n = 10^4일 때는 n(n-1)/2번, 즉 약 5 × 10^7번 비교해야 합니다. 정렬하면 같은 값들이 서로 이웃하게 되고, 해시 집합을 사용하면 평균적으로 O(1)에 질문에 답할 수 있어 한 번만 순회하면 됩니다.
정렬한 다음 이웃한 항목을 비교하세요
핵심 아이디어
정렬된 배열에서는 같은 값이 서로 옆에 놓입니다. [3, 1, 4, 1, 5]를 정렬하면 [1, 1, 3, 4, 5]가 되고, 이제 두 1이 서로 붙어 있습니다. 따라서 정렬한 다음에는 각 값을 바로 앞에 있는 값과만 비교하면 됩니다. 모든 쌍을 확인할 때 필요한 n(n-1)/2번 대신 n-1번 비교하면 됩니다.
이웃한 값이 같은 경우가 없다면 어디에도 같은 값이 없습니다. 정렬된 순서에서 x 두 개 사이에 있는 값은 x 이상이면서 동시에 x 이하여야 하므로, 그 값도 또 다른 x여야 합니다.
시간 복잡도는 정렬이 지배하므로 O(n log n)입니다. nums를 제자리에서 정렬하면 추가 배열이 필요하지 않지만, 호출한 쪽의 입력 순서가 바뀝니다. 입력을 변경하면 안 되는 경우에는 복사본을 정렬해야 하며, 이때 O(n)의 공간이 필요합니다.
알고리즘
nums를 오름차순으로 정렬합니다.i를 1부터 마지막 인덱스까지 반복합니다.nums[i]가nums[i-1]와 같으면true를 반환합니다.- 반복문이 끝난 후
false를 반환합니다.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return False해시 집합을 사용한 한 번의 순회
핵심 아이디어
배열을 한 번 순회하면서 지금까지 확인한 모든 값을 해시 집합에 저장합니다. 값을 추가하기 전에 집합에 이미 있는지 확인합니다. [3, 1, 4, 1, 5]의 경우 집합은 {3, 1, 4}까지 커지고, 두 번째 1이 나오면 집합에 이미 있으므로 5를 읽지 않고 true를 반환합니다.
집합에는 항상 현재 위치 이전에 나온 값만 정확히 저장되므로, 값이 발견되면 현재 값이 앞서 나온 적이 있다는 뜻이며, 발견하지 못한 채 끝까지 도달하면 모든 값이 서로 다르다는 뜻입니다.
해시 집합에서 값을 검색하고 삽입하는 데는 평균적으로 O(1) 시간이 걸리므로, 전체 순회는 O(n)입니다. 대신 메모리가 필요합니다. 반복되는 값이 없다면 집합에는 결국 n개의 값이 모두 저장됩니다.
알고리즘
- 빈 해시 집합
seen을 만듭니다. nums의 각 값에 대해, 그 값이seen에 있으면true를 반환합니다.- 그렇지 않으면 해당 값을
seen에 추가합니다. - 반복문이 끝난 후
false를 반환합니다.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
함정과 경계 사례
로직은 간단하므로 버그는 반복문의 경계와 비교 대상에 있습니다.
- 내부 반복문을
j = i에서 시작해 모든 쌍을 비교하는 경우. 그러면 각 값은 자기 자신과 일치하므로 결과는 항상true입니다. - 먼저 정렬하지 않고 이웃한 값들을 비교하는 경우.
[9, 1, 2, 3, 9]에서는 두9가 서로 이웃하지 않습니다. - 이웃 값을 비교하는 반복문을 인덱스 0에서 시작해
nums[-1]을 읽는 경우. 인덱스 1에서 시작해야 하며, 값이 하나인 배열은 올바르게false를 반환합니다. - 예를 들어
abs(x)를 해시하는 식으로 절댓값이 같은 값을 같은 것으로 취급하는 경우.-4와4는 서로 다른 숫자입니다. x - y를 반환하는 C 정렬 비교 함수를 작성하는 경우. 여기서는 차이가±2 × 10^9이내로 유지되어int의 한계인2^31-1 = 2147483647보다 작으므로 우연히 범위 안에 들어갑니다. 하지만int의 한계에 가까운 값을 사용하면 오버플로가 발생해 정렬 결과가 잘못됩니다. 대신(x > y) - (x < y)를 반환하세요.
자주 묻는 질문4
중복 항목 확인의 시간 복잡도는 얼마인가요?
해시 집합을 사용하는 해결 방법은 평균적으로 O(n) 시간이 걸리고 O(n)의 추가 공간을 사용합니다. 먼저 정렬하면 O(n log n) 시간이 걸리며 입력을 재정렬해도 된다면 추가 배열이 필요하지 않습니다. 모든 쌍을 비교하면 O(n²) 시간이 걸립니다.
추가 공간 없이 Contains Duplicate 문제를 풀 수 있나요?
네, 배열의 순서를 바꿔도 된다면 제자리에서 정렬한 다음 각 값을 이웃한 값과 비교하면 됩니다. 이렇게 하면 O(n) 집합 대신 O(n log n) 시간이 듭니다. 순서를 바꾸지 않고 추가 메모리도 사용하지 않는다면, 남는 유일한 방법은 O(n²) 쌍 검사입니다.
해시 집합을 사용하면 확인이 왜 빠를까요?
해시 집합은 값의 해시를 기준으로 값을 저장하므로, 값이 들어 있는지 확인하는 데는 순회하는 대신 평균적으로 상수 시간이 걸립니다. 각 요소마다 조회와 삽입이 한 번씩 필요하므로 전체 순회는 선형 시간이 걸립니다.
집합의 크기를 배열의 길이와 비교하는 것이 유효한 해결책인가요?
네. nums의 모든 요소로 집합을 만들고 그 크기가 배열보다 작은지 확인하면 O(n) 시간에 정답을 구할 수 있습니다. 루프 버전은 첫 번째 중복 요소를 만나는 즉시 반환하므로 대개 더 효율적입니다. 반면 집합을 모두 만들면 항상 모든 값을 읽습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def containsDuplicate(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [3, 1, 4, 1, 5]
기대값
true