Leetcode 136. Single Number (Easy)

 

이번 문제의 입력값은 숫자로된 배열 인데 모두 쌍으로 되어 있고 하나만 single value 입니다.

이 입력값 중 single value인 것을 찾아 내면 됩니다.

 

첫번째 접근법은 add 와 remove가 가능한 ArrayList()를 사용하는 것입니다. 

ArrayList()의 contains() 메소드도 이용하겠습니다.

빈 ArrayList()를 만들어 놓 고 입력된 배열의 크기만큼 for 문을 돕니다.

 

만들어 좋은 ArrayList에 있는 값하고 i 번째 값을 비교해서 contain 하고 있다면 이것은 쌍이니까 이 ArrayList에 있는 값을 remove 합니다.

Contain 하고 있지 않다면 아직 쌍이 아닐 확률이 있으니까 이 array list에 add 합니다.

For 문을 모두 돌고 나면 single인 값 하나만 있을 겁니다.

 

이것을 코딩하면 아래와 같습니다.

 

class Solution {
  public int singleNumber(int[] nums) {
    List<Integer> no_duplicate_list = new ArrayList<>();

    for (int i : nums) {
      if (!no_duplicate_list.contains(i)) {
        no_duplicate_list.add(i);
      } else {
        no_duplicate_list.remove(new Integer(i));
      }
    }
    return no_duplicate_list.get(0);
  }
}

 

다음 방법은 key, value 쌍으로 되어 있는 HashMap을 사용하는 방법이다.

이 HashMap의 put(), getOrDefault(), get() 메소드를 사용할 것이다.

HashMap에서 제공되는 메소드들은 아래에 링크에서 살펴 볼 수 있다.

 

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

HashMap (Java Platform SE 8 )

이중 getOrDefault에 대한 설명은 아래와 같다.

 

다시 원래 문제로 돌아가서 HashMap을 사용해서 만든 코드를 분석해 보겠다.

 

class Solution {
  public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> hash_table = new HashMap<>();

    for (int i : nums) {
      hash_table.put(i, hash_table.getOrDefault(i, 0) + 1);
    }
    for (int i : nums) {
      if (hash_table.get(i) == 1) {
        return i;
      }
    }
    return 0;
  }
}

 

입력된 배열의 크기만큼 for문을 돌리면서 각 값들을 key 로 put 합니다.

그리고 value 부분에는 getOrDefault를 사용해서 key 값이 없으면 0+1 즉 1이 할당이 되고 있으면 그 값에 +1을 해 줍니다.

이렇게 되면 중복된 값은 value부분에 2가 될 것이고 중복되지 않은 값은 value가 1 인 채로 끝까지 남아 있을 겁니다.

여기서 HashMap의 특징을 알아야 하는데요.

해쉬맵에서 키 값의 중복은 허용되지 않습니다.

그러니까 첫번째 for문에서 기존에 key가 존재 하면 그 key에 value를 덮어 쓰게 됩니다.

그러니까 {2,1,2,1,4} 를 위 코드로 돌리면 HashMap은 이렇게 될 겁니다.

2 : 2

1 : 2

4 : 1

 

이런 상태에서 두번째 for 문을 돌려서 value가 1인 값을 찾으면 그 값은 4가 됩니다.

 

이렇게 되면 첫번째 방법보다 runtime 줄어드는 효과가 있습니다. 왜냐하면 첫번째 방법은 for문 안의 contains()에서 아이템을 모두 살펴봐야 하기 때문에 time complexity가 O(n의 제곱)인데 반해서 두번째 접근 법은 O(n)입니다.

 

위 3줄의 Runtime이 아래 3줄보다 훨씬 효율적인 것을 볼 수 있습니다.

 

 

세번째는 수학을 이용하는 방법 입니다.

 

코드는 아래와 같습니다.

class Solution {
  public int singleNumber(int[] nums) {
    int sumOfSet = 0, sumOfNums = 0;
    Set<Integer> set = new HashSet();

    for (int num : nums) {
      if (!set.contains(num)) {
        set.add(num);
        sumOfSet += num;
      }
      sumOfNums += num;
    }
    return 2 * sumOfSet - sumOfNums;
  }
}

 

위 수학식 중 (a+b+c)가 sumOfSet이 되고 (a+a+b+b+c) 가 sumOfNums가 됩니다.

For문 안의 첫번째 if 문에서 sumOfSet이 계산됩니다.

그리고 if문 밖에서 sumOfNums가 계산됩니다.

그 값을 이용해서 위 수학식의 계산을 그냥 return 해 주면 됩니다.

 

마지막 방법은 Bit Manipulation입니다.

저도 잘 모르겠는데.... 그냥 이렇게 있구나... 하고 넘어가야 할 것 같습니다.

코드는 아래와 같습니다.

 

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}

 

실행결과를 보면 위로 갈수록 Runtime이 줄어 드는 것을 볼 수 있습니다.

 

각 Approach의 파이썬 코드는 아래와 같습니다.

 

Python

 

Approach 1

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        no_duplicate_list = []
        for i in nums:
            if i not in no_duplicate_list:
                no_duplicate_list.append(i)
            else:
                no_duplicate_list.remove(i)
        return no_duplicate_list.pop()

 

Approach 2

from collections import defaultdict
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_table = defaultdict(int)
        for i in nums:
            hash_table[i] += 1
        
        for i in hash_table:
            if hash_table[i] == 1:
                return i

 

Approach 3

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return 2 * sum(set(nums)) - sum(nums)

 

Approach 4

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a