문제 링크
문제 설명
- 정수 배열 번호가 주어지면 배열에 두 번 이상 표시되는 값이 있으면 참으로 반환하고, 모든 요소가 구분되는 경우 거짓으로 반환합니다.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true풀이 전략
1. Brute Force (완전 탐색)
방법 설명
- 리스트의 모든 쌍을 비교하여 중복되는 요소가 있는지 확인하는 방식입니다. 리스트의 각 요소와 그 다음 요소들을 하나씩 비교합니다.
장점
- 구현이 매우 간단하며, 복잡한 자료구조나 추가적인 메모리를 필요로 하지 않습니다.
단점
- 시간 복잡도가 (O(n^2))로, 리스트의 길이가 길어질수록 실행 시간이 급격히 증가합니다.
- 큰 입력에 대해 비효율적이며, 실용적이지 않습니다.
2. Sorting (정렬)
방법 설명
- 리스트를 정렬한 다음, 인접한 요소들끼리 비교하여 중복된 값이 있는지 확인합니다. 정렬 후에는 인접한 요소들만 비교하면 되므로 한 번의 순회로 확인할 수 있습니다.
장점
- 시간 복잡도가 (O(n \log n))로, 완전 탐색보다 효율적입니다.
- 추가적인 자료구조가 필요하지 않아 메모리 사용이 적습니다.
단점
- 정렬을 해야 하므로 원본 리스트를 수정할 수 있습니다. 만약 원본 리스트를 유지해야 한다면, 추가로 복사본을 만들어야 합니다.
- 정렬 자체가 추가적인 계산 비용을 요구하므로, 정렬하는 것이 비효율적일 수 있습니다.
3. Hash Set (해시 집합)
방법 설명
- 집합(set)을 이용하여 중복 여부를 확인합니다. 각 요소를 순회하면서, 이미 집합에 있는 값이라면 중복이므로
True를 반환하고, 없다면 집합에 추가합니다.
장점
- 평균 시간 복잡도가 (O(n))로 매우 빠릅니다.
- 중복된 값이 있는지 효율적으로 확인할 수 있으며, 추가적인 자료구조로
set을 사용하여 간결한 코드 작성이 가능합니다.
단점
- 추가적인 메모리 사용이 필요합니다. 특히 리스트에 모든 요소가 다르면, 모든 요소를 집합에 저장해야 하므로 메모리를 많이 사용할 수 있습니다.
- 리스트의 요소들이 해시 가능해야 한다는 전제 조건이 필요합니다.
4. Hash Map (해시 맵)
방법 설명
- 딕셔너리(Hash Map)를 이용하여 각 요소의 등장 횟수를 저장한 후, 2회 이상 등장한 요소가 있는지 확인하는 방법입니다.
장점
- 시간 복잡도가 (O(n))로 빠르며, 딕셔너리를 사용하여 각 요소의 중복 여부를 효율적으로 확인할 수 있습니다.
- 리스트 내에서 요소가 몇 번 등장했는지도 확인할 수 있습니다.
단점
- 메모리를 추가로 사용해야 하며, 모든 요소가 다르면 딕셔너리에 전체 요소가 저장되므로 메모리 부담이 커질 수 있습니다.
set방식보다 약간 복잡하며, 단순히 중복 여부만 확인할 때는 비효율적입니다.
요약
- Brute Force: 구현이 간단하지만, 시간 복잡도가 (O(n^2))로 비효율적임.
- Sorting: (O(n \log n)) 시간 복잡도로 비교적 빠르지만, 원본 리스트가 수정됩니다.
- Hash Set: 평균적으로 (O(n))의 시간 복잡도로 효율적이고 코드가 간결합니다. 메모리 사용량은 다소 증가.
- Hash Map: (O(n))의 시간 복잡도이며, 등장 횟수를 확인할 수 있지만 메모리 사용이 다소 증가.
일반적으로 중복 확인만 필요하다면 Hash Set이 가장 간결하고 빠른 선택입니다.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set() # 이미 확인한 숫자를 저장하기 위한 집합
for num in nums:
if num in seen: # num이 이미 seen에 존재하면 중복된 값이 있다는 뜻이므로 True 반환
return True
seen.add(num) # num이 중복되지 않았으면 seen에 추가
return False # 중복된 값이 없는 경우 False 반환
코드 분석
seen이라는 빈 집합(set)을 초기화합니다. 집합은 중복된 요소를 허용하지 않으므로, 중복 여부를 확인할 때 효율적입니다.nums리스트의 각 숫자num에 대해 반복문을 실행합니다.if num in seen:num이 이미seen에 있으면, 이는 중복된 숫자가 있다는 의미이므로True를 반환합니다.
seen.add(num):num이seen에 없다면seen에 추가하여, 이후 반복에서num이 다시 나오면 중복으로 인식할 수 있도록 합니다.
- 반복이 끝날 때까지 중복된 숫자가 없다면
False를 반환합니다.
코드의 장점
이 코드의 장점은 간결하고, 효율적인 중복 검사를 한다는 점입니다. 딕셔너리 대신 집합을 사용하므로 메모리 사용량이 줄어들고, in 연산을 통해 빠르게 중복을 확인할 수 있습니다.
해당 코드는 따로 print를 찍어볼 필요가 없다.
for을 돌리면서 set이라는 중복 요소를 허용하지 않는 자료형에 데이터를 입력하고
매 라운드 마다 set에 저장된 값과 비교를 하며 조건을 만족하면 바로 결과를 출력한다.