반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

카테고리

Leetcode 136. Single Number (Easy)

2022. 9. 30. 03:32 | Posted by 솔웅


반응형

 

이번 문제의 입력값은 숫자로된 배열 인데 모두 쌍으로 되어 있고 하나만 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 )

If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null. If the function returns null no mapping is recorded. If the function

docs.oracle.com

이중 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

 

 

반응형