코딩테스트 문제를 풀어보다가 새로운 자극을 얻게 된 문제가 있어 오랜만에 코딩테스트 글을 정리해본다.
Given a non-empty array of integers
nums
, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.비어 있지 않은 정수 nums 배열이 주어지면, 모든 요소가 하나를 제외하고 두 번 나타납니다. 그 하나를 찾으세요. 선형 런타임 복잡도를 가진 솔루션을 구현하고 상수 추가 공간만 사용해야 합니다.
✅ 선형 런타임 복잡도
알고리즘의 실행 시간이 입력 데이터 크기(n)에 비례해 증가하는 것으로, 입력 데이터의 크기가 커질수록 실행 시간도 그만큼 증가한다.
빅오 표기법 -
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
1 <= nums.length <= 3 * 10⁴
3 * 10⁴ <= nums[i] <= 3 * 10⁴
class Solution {
public int singleNumber(int[] nums) {
if(nums.length == 1) return nums[0];
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int key : map.keySet()) {
if(map.get(key) == 1) return key;
}
return nums[0];
}
}
문제를 읽고 먼저 단순하게 생각나는 대로 풀어본 코드이다.
제약사항이 nums.length
가 최대 3 * 10⁴ 이어서 (= 10⁸) 가 넘지 않도록 한 번의 nums
반복을 돌렸다.
nums
의 num
은 map
에 최대 2의 value
가 존재할 것이다.map
을 반복하면서 value
가 1 인 key
를 반환한다.nums
에는 한 숫자당 최대 2번 들어가 있기 때문에 map
에는 최소 nums.length / 2
만큼의 key
를 갖고 있을 것이다. nums.length
가 여러번 반복하는 최악의 상황은 면하지만 map
자체로도 상당히 많은 key
를 가지고 있기 때문에 두 번의 반복문이 상당히 비효율적으로 느껴졌다.
Submit 해 봤더니 13ms 가 측정됐다. 🫨
13ms 는 그냥 넘어갈 수 없다 … 하지만 마땅한 다른 풀이가 떠오르지 않는다.
최소 실행시간으로 측정된 다른 사람들의 코드를 참고했다.
class Solution {
public int singleNumber(int[] nums) {
int result=0;
for(int num:nums){
result ^=num;
}
return result;
}
}
나는 사용한 적이 극히 드물었던 ^=
계산식을 사용했다.
한 숫자 당 2번의 중복이 있는 배열 내에서 중복이 없는 숫자를 거르기 위한 방법으로 해당 계산식을 도출해 낼 수 있다는 게 대단하다고 느껴지면서 아직 나는 좀 더 생각의 범위를 넓혀야되겠다는 생각이 들었다.
^=
는 XOR 연산으로, 아래와 같은 특징을 가진다.
a ^ a = 0
: 동일한 숫자를 XOR하면 결과는 0이다.a ^ 0 = a
: 어떤 숫자와 0을 XOR하면 결과는 원래 숫자이다.(a ^ b) ^ c = a ^ (b ^ c)
: 순서에 관계 없이 교환과 결합이 자유롭다.nums = {4, 1, 2, 1, 2}
일 경우 처리 순서는 아래와 같다.
result = 0
result ^= 4
→ 0 ^ 4 = 4
result ^= 1
→ 4 ^ 1 = 5
(0100 ^ 0001 = 0101)result ^= 2
→ 5 ^ 2 = 7
(0101 ^ 0010 = 0111)result ^= 1
→ 7 ^ 1 = 6
(0111 ^ 0001 = 0110)result ^= 2
→ 6 ^ 2 = 4
(0110 ^ 0010 = 0100)4 ^ 1 ^ 2 ^ 1 ^ 2
는 교환법칙 및 결합법칙에 따라 1 ^ 1 ^ 2 ^ 2 ^ 4
로 보면 더 이해가 간다.
(1 ^ 1) = 0
, (2 ^ 2) = 0
이기 때문에(같은 숫자의 XOR 연산 결과는 0이기 때문에) 두 번 중복해서 XOR 연산되는 숫자는 0으로 상쇄되고 중복되지 않는 숫자만 남게 되는 것이다.
생각의 확장이 필요하다고 느끼게 해준 문제와 풀이였다.