[LeetCode] 2150. Find All Lonely Numbers in the Array

- Problem

2150. Find All Lonely Numbers in the Array

You are given an integer array nums. A number x is lonely when it appears only once, and no adjacent numbers (i.e. x + 1 and x - 1) appear in the array.

Return all lonely numbers in nums. You may return the answer in any order.

Example 1:

Input: nums = [10,6,5,8]
Output: [10,8]
Explanation: 
- 10 is a lonely number since it appears exactly once and 9 and 11 does not appear in nums.
- 8 is a lonely number since it appears exactly once and 7 and 9 does not appear in nums.
- 5 is not a lonely number since 6 appears in nums and vice versa.
Hence, the lonely numbers in nums are [10, 8].
Note that [8, 10] may also be returned.

Example 2:

Input: nums = [1,3,5,3]
Output: [1,5]
Explanation: 
- 1 is a lonely number since it appears exactly once and 0 and 2 does not appear in nums.
- 5 is a lonely number since it appears exactly once and 4 and 6 does not appear in nums.
- 3 is not a lonely number since it appears twice.
Hence, the lonely numbers in nums are [1, 5].
Note that [5, 1] may also be returned.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^6

---

주어진 배열 nums 에서 Lonely Number를 찾는 문제이다.
여기서 Lonely number는 전체 배열에서 x를 포함한 x+1, x-1이 존재하지 않을 때 Lonely Number임을 정의한다.

예를 들어, 배열 [3,5,6,7] 에서 3은 2나 4가 존재하지 않기에 Lonely number이다. 반면에, 6은 5와 7이 존재하기에 Lonely하지 않다. Lonely night~
마찬가지로 원소 5 또한 6이 존재하고, 7 또한 6이 존재하기에 Not lonely number이다. 즉, 배열 [3,5,6,7] 의 Lonely number는 3 하나이다.

문제의 주어진 조건을 본다면, 주어진 배열 nums의 최대 길이는 10^5이다. brute-force 로도 해답을 찾을 수는 있지만 굉장히 비효율적일 것이다.
brute-force로 대략적인 코드를 짜보자면 다음과 같을 것이다.

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        N = len(nums)
        answer = set()
        
        for i in range(N):
            number = nums[i]
            for j in range(N):
                if i == j: continue
                if nums[j] - 1 == number or nums[j] + 1 == number or nums[j] == number:
                    break
            else:
                answer.add(number)
        
        return answer

이중 포문을 이용하여 전체 케이스에 대해서 탐색을 해야한다. 즉, 시간 복잡도 O(N^2)를 가질 것이다. (아니나 다를까 이 코드로 제출 시 시간 초과💣)

그렇다면, 이 문제는 O(NlogN) 혹은 O(N)을 만족하는 로직을 찾아야 한다.

- 내 풀이 1

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        counter_nums = collections.Counter(nums)
        num_once_list = [k for k, v in counter_nums.items() if v == 1]
        answer = []
        
        for num in num_once_list:
            if counter_nums[num-1] or counter_nums[num+1]:
                continue
            answer.append(num)
        
        return answer

풀이는 다음과 같다.

1. counter 모듈을 이용하여 주어진 배열 nums의 각 원소 빈도를 계산한다.
2. 숫자가 한 번만 나온 num_once_list를 추출한다.
   • 가령 [3,3,5,6,7]이라는 배열이 주어진다면 원소 3은 x+1 혹은 x-1 값인 2, 4를 가지고 있진 않지만, 중복 원소인 3을 가지게 된다. 즉, 3은 Lonely number로 정의되지 않는다.
   • 따라서, 중복이 있는 원소를 제거하여 배열을 만든다. [3,3,5,6,7]이라는 배열은 [5,6,7]이라는 배열이 된다.
3. num_once_list를 돌며 x-1 혹은 x+1이라는 값이 있는지 판별한다.
   • 이 때, Counter 모듈을 사용하였기에 O(1)의 시간 복잡도로 조건문을 판별할 수 있게 된다.

결과적으로, O(N)을 만족하는 풀이이다.

- 내 풀이 2

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        c_nums = collections.Counter(nums) # O(N)
        set_nums = set(nums)
        return [num for num in set_nums if not c_nums[num-1] + c_nums[num+1] and c_nums[num] == 1] # O(N)           

깔끔한 코드를 위해 조금 더 파이썬스럽게 풀어보았다.

- 결과