•
문제 설명 : 제공된 nums로 만들 수 있는 조건(|x - y| <= min(x, y)) 에 맞는 쌍들로 만들 수 있는 가장 큰 XOR 값을 반환
•
풀이 방법
◦
단순 구현은 FOR문을 사용한 O(N^2) 방식이다.
▪
이 방법으로도 통과가 되지만, hash_table을 사용한 방법은 아니라서 hash_table을 사용한 방법을 찾아보았다.
•
시간복잡도 :
•
성공 코드
class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
max_xor = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
if abs(nums[i] - nums[j]) <= min(nums[i], nums[j]):
max_xor = max(max_xor, nums[i]^nums[j])
return max_xor
Python
복사
•
개선된 성공 코드
동일하게 중복 For문을 사용하는 것은 차이가 없다.
하지만, 내부 For의 범위가 Set을 사용한 방식으로 변경하여 탐색 범위가 줄어든 것을 알 수 있다.
만약 nums 가 [1,1,1,1,1,1,1,1,1,1,2,10] 처럼 중복 값이 많은 형태로 전달된다면 많은 시간을 감소시킬 수 있을 것이다.
파이썬 set의 데이터구조부터 hashtable까지(갑분 C 등장)
위 블로그에 잘 설명되어 있는데, set 도 해시테이블을 사용한 데이터 타입이다.
물론 value 가 존재하지 않는 점에서 dict 와 큰 차이가 있다.
그래서 아래 코드를 dict를 사용한 코드로 바꿔도 문제는 없다.
다만, dict로 사용했을 때 value를 설정할 필요가 없기 때문에 set 방식이 조금 더 가독성이 좋다.class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
max_xor = 0
num_set = set()
for num in nums:
for x in num_set:
if abs(num - x) <= min(num, x):
max_xor = max(max_xor, num ^ x)
num_set.add(num)
return max_xor
Python
복사