[LeetCode] Check If N and Its Double Exist

목차

문제

• arr안에서 다음 조건을 만족하는 인덱스 쌍이 존재하는지 체크하는 문제입니다.
  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]
• 예시

  • Input: arr = [10,2,5,3]
    Output: true
    Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

  • Input: arr = [3,1,7,11]
    Output: false
    Explanation: There is no i and j that satisfy the conditions.

• 제약조건
  • 2 <= arr.length <= 500
  • -103 <= arr[i] <= 103

문제 풀이

풀이 1 : 완전 탐색

• 풀이
  • 단순하게 두 개의 for문을 사용해서 풀 수 있습니다.
• 코드

  • class Solution:
        def checkIfExist(self, arr: List[int]) -> bool:
            n = len(arr)
            flag = False
            for i in range(n):
                for j in range(i+1,n):
                    if arr[i]==2*arr[j] or arr[i]*2==arr[j]:
                        flag = True
                        break
                if flag:
                    break
            return flag

• 시간복잡도
  • O(N^2)으로 비효율적입니다.

풀이 2 : 해쉬테이블 이용

• 풀이
  • Counter을 이용하여 배열값들에 대한 개수를 체크해 주는 딕셔너리를 생성합니다.
  • 그 후 배열의 모든 원소값을 체크하면서 딕셔너리 키 중 2배가 되는 값이 있는지 체크를 진행합니다.
  • 이때 0의 경우 원소가 2개 있을 경우 0 *2 = 0이므로 따로 처리해주어야 합니다.
• 코드

  • from collections import Counter
    
    class Solution:
        def checkIfExist(self, arr: List[int]) -> bool:
    
            counter = Counter(arr)
    
            #check if there are more than one zeros
            if counter[0]>=2:
                return True
    
            for num in arr:
                if counter[2*num] and num!=0:
                    return True
            return False

• 시간복잡도
  • O(N)으로 해결이 가능해집니다.

알게 된 내용

• 특정 원소끼리의 값을 비교하거나 체크할 때 해쉬테이블을 이용하면 O(N)만에 빠르게 해결할 수 있습니다.

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/527/searching-for-items-in-an-array/3250/