Home Single Number
Post
Cancel

Single Number

Leetcode Problem

Single Number

정수들의 모여 있는 배열에서 한 개만 있는 정수를 출력하는 문제입니다.

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        arr = [0] * 60001
        for n in nums:
            arr[n + 30001] += 1
        return arr.index(1) - 30001

정수의 범위가 -30000 ~ 30000까지이므로 60001개의 배열을 생성한 후 배열에 있는 정수를 index로 활용하여 배열의 정수들의 개수를 셉니다.
이렇게 하면 중복되는 수들은 2, 4, 6, … 등의 짝수로 배열의 값을 가지고 한 개만 있는 정수는 arr[정수] = 1로 나타나니, arr의 값이 1인 index를 반환하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        arr = {}
        for n in nums:
            if n in arr.keys():
                arr[n] += 1  
            else:
                arr[n] = 1
        for key in arr.keys():          
            if arr[key] == 1:
                return key

논리가 좀 비효율적인 것 같아서 dictionary 자료형을 활용하여 다시 풀어봤습니다.
하지만 속도는 이 방법이 더 느렸습니다.

1
2
3
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)

solution에서 본 풀이입니다.
한 줄도 아니고 한 단어로 끝내버렸습니다. ㅋㅋ
xor bit 연산을 통해 정수가 두 번 이상 나오면 0이 되고 마지막 하나 남은 수만 남게 됩니다.

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        r = 0
        for n in nums:
            r = r ^ n
        return r

xor 연산을 활용하면서 가독성을 좋게 한다면, 이런 식으로도 풀 수 있습니다.





참고

This post is licensed under CC BY 4.0 by the author.