Today I Learned

오늘도 코테!

---

136. Single Number

https://leetcode.com/problems/single-number/description/

문제

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.

Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4

---

풀이과정 & Java 코드

• 매우 간단한 문제처럼 보이지만 생각할 것이 많은 문제였다.
  시간복잡도를 생각 안하면 그냥 리스트 하나 더 만들어서 중복체크하면 끝나는 문제지만, a linear runtime complexity and use only constant extra space라는 제약조건이 달려있다.
  그래서 시간복잡도를 줄이기 위해 여러 시도를 해보았다.

1. sort

  public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length-1; i+=2) {
      if (nums[i]!=nums[i+1]) return nums[i];
    }
    return nums[nums.length-1];
  }

• 우선 sort를 한 후 순회 한 번을 통해 검증하는 방식으로 풀었다.
  sort 후 (0,1) (2,3) 이렇게 두 값들은 같아야 하고, 쌍이 안지어지는 값이 답이 되는 구조이다.

• 뒤의 순회는 간단하지만, sort에서 이미 O(n log n)이 소모되기 때문에 문제에서 원하는 답은 아니었다.

---

2. map

  public int singleNumber(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      map.put(nums[i],map.getOrDefault(nums[i],0)+1);
    }
    for (int num : nums) {
      if (map.get(num) == 1) return num;
    }
    return 0;
  }

• 시간복잡도에서 이득을 보기위해 공간복잡도를 늘리는 방법을 사용했다.
  map을 만들어 한 번의 순회동안 key에 nums의 값을, value에 해당 값이 나온 횟수를 getOrDefault() 메서드를 이용해 구현했다.
  그 후 map을 한번 순회하면서 value가 1인 key를 반환하면 완료.

• 시간복잡도 상으로는 위의 sort가 O(n log n)이고, 이 경우가 O(n)밖에 소모되지 않는다. 하지만 정작 결과를 돌려보니 13ms로 오히려 위의 케이스보다 속도가 더 느렸다. 다른 자료구조를 활용하다보니 지체가 발생하는 것 같았다.

---

3. XOR

  public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
      result ^= num;
    }
    return result;
  }

• 문제에서 원하는 답이 뭘까하고 검색하던 중, 비트 연산에서 XOR을 활용하는 방법을 찾았다.

• XOR 연산은 두 비트가 서로 다를 때 1을 반환하고, 같을 때는 0을 반환한다. XOR 연산은 교환 법칙과 결합 법칙이 성립하므로, 어떤 순서로 비트를 XOR해도 결과가 같다.
  그러므로 배열의 모든 요소를 XOR 연산하면, 등장 횟수가 2인 숫자들은 상쇄되어 결과적으로는 등장 횟수가 1인 숫자만 남게되는 것이다.

• 연산자 ^를 이용해 for문으로 ^(XOR)연산을 계속 누적시켜 결국 남는 값을 return하면 정말 간단하게 완료되는 것이다.

• 간단한 연산 한번으로 1ms만에 완료되었다.