Single Number
각 값이 정확히 두 번씩 나타나는 nums 목록이 주어지지만, 값 하나는 한 번만 나타납니다. 한 번만 나타나는 값을 반환하세요.
함수
- numsinteger-array
- 하나를 제외한 모든 값이 두 번씩 나타나는 목록
- 반환값integer
- 한 번만 나타나는 값
제약 조건
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- 모든 값은 정확히 두 번씩 나타나며, 단 하나의 값만 정확히 한 번 나타납니다.
예제
- 입력
- nums = [8, 3, 8]
- 출력
- 3
- 설명
- 8은 두 번 나타나고 3은 한 번 나타나므로 답은 3입니다.
- 입력
- nums = [5, -2, 7, 5, 7]
- 출력
- -2
- 설명
- 5와 7은 각각 두 번 나타나고, -2는 한 번만 나타나는 값입니다. 음수 답도 양수 답과 같은 방법으로 찾습니다.
- 입력
- nums = [42]
- 출력
- 42
- 설명
- 값이 하나인 목록에는 쌍이 전혀 없으므로 그 값이 정답입니다.
제출 시 숨은 테스트 +13개
후속 질문
모든 값이 하나만 제외하고 세 번씩 나타난다면 어떨까요? XOR만으로는 더 이상 세 번 나타나는 값들이 상쇄되지 않습니다. 그래도 O(n) 시간과 O(1) 추가 메모리로 유일한 값을 찾을 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
모든 같은 값의 쌍을 사라지게 만들 수 있다면, 답만 남을 것입니다. 같은 숫자 두 개를 아무것도 아닌 것으로 만드는 연산이 있을까요?
XOR 연산은 다음과 같습니다.
x ^ x는0이고x ^ 0은x입니다. 또한 순서에 구애받지 않으므로, 값의 두 복사본이 상쇄되기 위해 서로 나란히 있을 필요는 없습니다.0에서 시작하는 변수 하나를 유지하세요.nums의 모든 값을 그 변수에 XOR한 다음, 그 값을 반환하세요. 맵이나 정렬은 필요하지 않습니다.
풀이
짝이 없는 값 하나를 찾는 것은 세기 문제이며, 해시 맵은 한 번의 순회로 모든 값을 셉니다. 문제는 메모리입니다. 맵은 목록의 크기에 따라 커집니다. XOR은 아예 셀 필요를 없애 줍니다. 값을 자기 자신과 XOR 연산하면 0이 되기 때문입니다. 목록 전체를 XOR 연산하면 모든 쌍이 서로 상쇄되어, 한 번의 순회와 변수 하나만으로 단일 값이 남습니다.
각 값을 훑어보며 세세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
각 값을 차례로 선택하고 전체 목록을 훑으며 해당 값이 몇 번 나타나는지 셉니다. 쌍을 이루는 값은 2로 셉니다. 하나뿐인 값은 1로 세므로, 개수가 1인 첫 번째 값을 반환합니다.
정답의 정의에서 개수가 직접 도출되고 카운터 외에는 추가 메모리가 필요하지 않으므로 올바른 방법입니다.
n개의 각 값에 대해 n개의 값을 모두 훑기 때문에 느립니다. 하나뿐인 값이 9,999개로 이루어진 목록의 끝에 있으면 비교 횟수는 거의 10^8번입니다.
알고리즘
nums의 각 값을 반복합니다.- 전체 목록을 훑으며 해당 값과 같은 값의 개수를 셉니다.
- 개수가 1이면 해당 값을 반환합니다.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0해시 맵으로 세기
핵심 아이디어
모든 값마다 목록을 다시 검색하면 작업이 반복됩니다. 대신 한 번 순회하면서 모든 값의 개수를 세세요. 값에서 개수로 매핑하는 해시 맵을 사용하고, 각 단계에서 현재 값의 개수에 1을 더합니다.
[5, -2, 7, 5, 7]의 경우 맵에는 최종적으로 5 → 2, -2 → 1, 7 → 2가 저장됩니다. 맵을 두 번째로 순회하면 개수가 1인 항목을 찾을 수 있으며, 그 값은 -2입니다.
각 값에 대해 맵을 한 번 갱신하므로 시간 복잡도는 O(n)입니다. 맵에는 약 n/2개의 항목이 저장되므로 추가 메모리 복잡도는 O(n)입니다. 내장 맵이 없는 C에서는 value + 10^4를 인덱스로 사용하는 카운터 배열이 값의 범위가 작기 때문에 같은 역할을 합니다.
알고리즘
- 값에서 개수로 매핑하는 빈 맵을 만드세요.
nums의 각 값에 대해 해당 값의 개수에 1을 더하세요.- 맵을 순회하며 개수가 1인 값을 반환하세요.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR 모든 값을
핵심 아이디어
XOR는 두 숫자를 비트 단위로 비교해 서로 다른 위치의 비트를 설정합니다. 다음 세 가지 사실을 얻을 수 있습니다. x ^ x = 0, x ^ 0 = x이며, 연산 순서는 중요하지 않습니다.
따라서 전체 목록의 값을 0으로 시작하는 하나의 변수에 XOR 연산하세요. 각 쌍이 서로 짝을 이루도록 연산을 재그룹화할 수 있으며, 모든 쌍은 0이 됩니다. 그러면 0 ^ single만 남고, 이는 단일 값입니다. [8, 3, 8]의 경우: 0 ^ 8 = 8, 다음으로 8 ^ 3 = 11, 그다음 11 ^ 8 = 3입니다.
음수도 작동합니다. XOR는 2의 보수 형식의 비트에 작용하며, 서로 같은 두 음수는 비트도 같으므로 다른 쌍과 마찬가지로 서로 상쇄됩니다. 반복문은 각 값을 한 번씩 읽고 변수 하나만 유지합니다. 시간 복잡도는 O(n)이고 추가 메모리 복잡도는 O(1)입니다.
알고리즘
result를 0으로 설정합니다.nums의 각 값에 대해result를result ^ value로 설정합니다.result를 반환합니다.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
함정과 경계 사례
XOR 반복문은 짧기 때문에, 실수는 시작 위치와 사람들이 대안으로 선택하는 방법에 숨어 있습니다.
result를nums[0]으로 초기화한 다음, 인덱스 0을 포함해 모든 값을 반복하는 것. 첫 번째 값이 XOR 연산에 두 번 포함되어 서로 상쇄됩니다. 0에서 시작하거나 인덱스 0을 건너뛰세요.- 정렬한 뒤 두 칸씩 이동하며 이웃한 값을 비교하고, 하나뿐인 값이 마지막 요소일 수 있다는 점을 잊는 것.
[1, 1, 2]에는 일치하지 않는 쌍이 없으며, 답은 남은 2입니다. 2 × sum(distinct values) - sum(nums)를 사용하는 것. 올바른 값을 구하지만, 서로 다른 값의 집합에는O(n)메모리가 필요하며 XOR 방식은 이를 피합니다.- XOR이 다른 개수에도 작동한다고 기대하는 것. XOR은 짝수 번 나타나는 값을 상쇄합니다. 어떤 값이 세 번 나타나면 하나가 남아 답을 틀리게 합니다.
자주 묻는 질문4
Single Number의 시간 복잡도는 무엇인가요?
XOR 방식은 각 값을 한 번씩 읽고 변수 하나만 유지하므로 O(n) 시간과 O(1) 추가 공간이 필요합니다. 해시 맵도 O(n) 시간이 걸리지만 O(n) 메모리가 필요합니다. 매번 새로 훑어 각 값을 세면 O(n²)이 걸립니다.
XOR는 왜 Single Number 문제를 해결할까요?
숫자를 자기 자신과 XOR하면 0이 되고, 0과 XOR하면 아무것도 바뀌지 않으며, 연산 순서는 중요하지 않습니다. 따라서 전체 목록을 XOR하면 각 쌍을 묶어 0으로 상쇄할 수 있습니다. 짝이 없는 값만 남습니다.
음수에서도 XOR 트릭이 작동하나요?
네. XOR은 숫자를 저장하는 비트에 적용되며, 음수는 2의 보수로 저장됩니다. 같은 음수 두 개는 비트가 동일하므로 양수와 마찬가지로 정확히 상쇄됩니다. [5, -2, 7, 5, 7]에서 결과는 -2입니다.
다른 값이 세 번 나타날 때는 어떻게 해결하나요?
XOR는 세 개가 아니라 쌍을 상쇄하므로, 여기서는 제대로 작동하지 않습니다. 대신 32개 비트 각각이 설정된 값이 몇 개인지 셉니다. 세 개씩 묶인 값은 3의 배수를 더하므로, 각 비트의 개수를 3으로 나눈 나머지가 단일 값의 해당 비트가 됩니다. 이 방법도 O(n) 시간과 O(1)의 추가 메모리로 실행됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def singleNumber(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [8, 3, 8]
기대값
3