[LeetCode] 1346. Check If N and Its Double Exist - Python

 

 

난이도: Easy

문제 설명

---

Given an array arr of integers, check if there exist two indices i and j such that :

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

 

문제 예제

---

Example 1:

Input: arr = [10,2,5,3]

Output: true

Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

 

Example 2:

Input: arr = [3,1,7,11]

Output: false

Explanation: There is no i and j that satisfy the conditions.

 

제한 사항

---

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

 

✏️ Solution(솔루션)

---

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        double_arr = defaultdict(list)

        for i, num in enumerate(arr):
            double_arr[2 * num].append(i)

        for i, num in enumerate(arr):
            if num in double_arr and double_arr[num] != [i]:
                return True
        
        return False

 

이 문제는 arr의 i번째 요소가 arr의 j번째 요소에 2를 곱한 값이랑 같으면 True를 반환하고 하나도 만족하는게 없으면 False를 반환하면 되는 문제 였다.

 

나는 딕셔너리를 사용해 문제를 해결했다.

 

먼저 각 arr요소에 2를 곱한 값을 딕셔너리의 키로 사용하였고, 값으로는 요소의 위치를 넣어주었다.

예를 들어, input arr이 [10, 2, 5, 3]이면 딕셔너리에는 다음과 같이 저장했다. --> {20: [0], 4: [1], 10: [2], 6: [3]}

 

그런다음 arr의 요소를 탐색해 요소가 딕셔너리의 키로 있으면서 위치가 다르다면 True를 반환하고, 모든 요소를 탐색했음에도 조건을 만족하는 것이 없으면 False를 반환하게 구현했다.

---

[LeetCode] 1346. Check If N and Its Double Exist