[Java][LeetCode] #2932. Maximum Strong Pair XOR I | O(nlogn) | O(n^2)

문제 / 예시 :

 

제한 조건 :

 

보자마자 복잡하다고 생각했지만!

풀어서 써보니 많이 복잡하진 않았다.

 

---

풀이 #1

내가 생각한 방법은

Array 를 정렬시키고, 

같은 숫자 (같은 위치) 면 위의 조건에 무조건 통과하니, 

투 포인트를 둬서 같은 위치에서 시작 하나씩 이동하면서 비교하는 것 이다.

 

예시로 보면,

1	2	3	4	5
Left  Right

이 위치에서 시작

1	2	3	4	5
Left	Right

nums[right] - nums[left] => nums[left]  에 해당 할 경우, XOR 값을 계산해주고 Right를 다음으로 넘기면 된다.

 

근데

1	2	3	4	5
Left		Right

이 경우, nums[right] - nums[left] => nums[left] 에 해당하지 않아서 Left를 다음으로 이동시키고, Right도 다시 left와 같은 위치에서 시작

1	2	3	4	5
	Left  Right

...

 

코드로 구현하면

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int maximum = 0, XORValue = 0;

        Arrays.sort(nums); // time complexity : O(nlogn)

        for (int leftIndex = 0; leftIndex < nums.length; leftIndex++) {
            int rightIndex = leftIndex;

            while (rightIndex < nums.length &&
                    nums[rightIndex] - nums[leftIndex] <= nums[leftIndex]) {
                XORValue = nums[rightIndex] ^ nums[leftIndex];
                maximum = Math.max(XORValue, maximum);
                rightIndex++;
            }
        }

        return maximum;
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

 

이렇게 깔끔하게 통과하는 것을 볼 수 있다.

 

근데 결과 값이 맘에 들지 않아서

가장 빠른 속도의 풀이를 참고하여 다시 풀어본 나의

 

#풀이2

for문 2개를 써서 모든 경우의 수를 조건문으로 비교하는 방법

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int maximum = 0;

        for(int leftNumber : nums) {
            for(int rightNumber : nums) {
                if((leftNumber ^ rightNumber) > maximum
                        && Math.abs(leftNumber - rightNumber) <= Math.min(leftNumber, rightNumber) ) {
                    maximum = leftNumber ^ rightNumber;
                }
            }
        }
        return maximum;
    }
}

Time Complexity: O(n^2)
Space Complexity: O(1)

 

시간 복잡도는 나의 풀이와 동일한데, 왜 더 빠른지 궁금해서 ChatGPT 한테 물어봤다.

 

그랬더니 이유가 

1. Optimized Looping: The enhanced for-loops used in the second implementation (for(int i : nums) and for(int j : nums)) might have been optimized more effectively by the compiler or runtime environment compared to the traditional loops used in the first implementation.
2. Simplified Logic: The second implementation may have had slightly fewer operations within the nested loops, leading to faster execution.
3. Processor and Memory Architecture: The actual hardware architecture of the processor and memory subsystem can also affect runtime performance. Certain operations may be more efficiently executed on specific hardware architectures.
4. Input Data Characteristics: The runtime performance can also depend on the specific characteristics of the input data. If the input data has certain patterns or properties that favor one implementation over the other, it can influence the runtime performance.

라고 알려주었다.

 

어렵구만..