2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 5월 31일 (금)
Leetcode daily problem
260. Single Number III
Problem
정수 배열 nums가 주어지면 정확히 두 개의 요소가 한 번만 나타나고 다른 모든 요소는 정확히 두 번 나타난다.
한 번만 나타나는 두 요소를 반환한다.
어떤 순서로든 답변을 반환해도 상관없다.
시간 복잡도 O(n), 공간복잡도 O(1) 로 해결해야 한다.
Solution
XOR operation
주어진 배열에서 두 번 나타나는 숫자들과 한 번 나타나나는 두 숫자가 있을 때, 한 번만 나타나는 두 숫자를 찾기 위한 핵심 아이디어는 XOR 연산을 사용하는 것이다.
XOR 연산은 두 비트가 다르면 1, 같으면 0이 되는 연산이다.
처음에 모든 숫자를 XOR 연산하면 두 개의 한 번만 나타나는 숫자를 제외한 나머지 숫자들은 두 번 나타나기 때문에 0이 된다. 그래서 남은 것은 한 번만 나타나는 두 숫자의 XOR 결과 이다.
위에서 계산한 모든 숫자를 XOR 한 결과에서 다른 비트를 찾아야 하는데, 그 이유는 해당 비트에서 두 숫자가 다른 부분을 나타내기 때문에 연산 전의 다른 두 숫자를 알 수 있기 때문이다.
예를 들어 주어진 배열이 [1,2,1,3,2,5] 였다고 한다면 모든 숫자를 XOR 하면 1^1^2^2^3^5 = 3^5가 된다.
3의 이진수는 0011, 5의 이진수는 0101이고,
3^5는 0110 이다. 즉 2번째와 3번째 비트가 달라서 0110이 나오는 것을 볼 수 있다.
여기서 비트가 달라서 나오는 맨 오른쪽의 1을 기준으로 배열을 두 그룹으로 나눈다. 가장 오른쪽에 나오는 1의 비트
'0010' 과 같은 숫자들 2,3 과 '0000' 과 같은 숫자들 1,5 로 나뉘게 된다.
- 예를 들면 3번째 비트가 1인 숫자 그룹: 2 (0010), 3 (0011), 2 (0010) => 2와 3
- 3번째 0인 숫자 그룹: 1 (0001), 1 (0001), 5 (0101) => 1과 5
각 그룹에서 XOR 연산을 하면 각 한 번만 나오는 숫자를 얻을 수 있다. 위의 첫 번째 그룹의 [2,2,3] 에서의 XOR 연산으로 3, 두 번째 그룹의 [1,1,5] 에서의 XOR 연산으로 5가 나와 [3,5] 가 나오게 된다.
Code
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for num in nums:
xor ^= num
diff_bit = xor & -xor
a,b = 0,0
for num in nums:
if num & diff_bit:
a ^= num
else:
b ^= num
return [a,b]
-
xor 변수에 모든 숫자를 XOR 연산한 값을 업데이트하고, diff_bit 변수로 xor 결과에서 가장 오른쪽에 있는 1비트를 찾는다.
-
여기서 가장 오른쪽에 있는 1비트를 찾는 연산은 'xor & -xor'로 찾을 수 있다.
: 이 비트는 두 숫자가 다른 위치를 나타낸다. -
배열을 두 그룹으로 나누고 각 그룹에서 XOR 연산을 수행한다. 각 그룹에서 두 번 나오는 숫자는 0이 나오게 되고 한 번 나타나는 숫자가 남는다.
[참고]
xor &-xor 이 가장 오른쪽에 있는 1인 비트를 찾는 방법인 이유
먼저 2의 보수에 대해 알아야 하는데, 2의 보수를 구하는 방법은 각 비트를 반전(0을 1로, 1을 0으로)하고, 1을 더하는 것이다. 예를 들어 6(0110)의 보수는
6의 이진수 0110
각 비트를 반전 1001
1을 더함 1010
즉, 1010은 -6을 이진수로 나타낸 값이다.
이제 xor과 -xor의 관계를 본다면
xor 인 6 (0110) 이라면, -xor은 1010 이다.
이 두 값을 and 연산을 해보면
0110 & 1010 = 0010 이 나오게 된다.
즉 xor과 -xor의 and 연산으로 가장 오른쪽에 있는 1비트를 찾을 수 있다.
Complexicity
시간 복잡도
모든 숫자를 XOR 하는 단계로 모든 배열을 탐색할 때 O(n)이 소요되고, 가장 오른쪽인 비트 연산을 찾는 비트 연산은 O(1) 이 소요되며, 배열을 두그룹으로 나누고 각 XOR 연산을 할 때는, 연산은 O(1) 이지만 배열을 그룹으로 나누기 위해 탐색하므로 O(n)이 소요된다.
즉, 전체 시간복잡도는 O(n) 이다.
공간 복잡도
추가적인 배열을 생성하지 않고, 모든 변수는 상수 공간을 차지해서 공간 복잡도는 O(1) 이다.
비트 연산 어지럽다
