[LeetCode] - 2441. Largest Positive Integer That Exists With Its Negative

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Largest Positive Integer That Exists With Its Negative" 문제입니다.

--> https://leetcode.com/problems/largest-positive-integer-that-exists-with-its-negative/description/

 

문제 : 

Given an integer array nums that does not contain any zeros, find the largest positive integer k such that -k also exists in the array.

Return the positive integer k.

If there is no such integer, return -1.

---

Example 1 :

Input : nums = [-1,2,-3,3]

Output : 3

Explanation : 3 is the only valid k we can find in the array.

 

Example 2 :

Input : nums = [-1,10,6,7,-7,1]

Output : 7

Explanation : Both 1 and 7 have their corresponding negative values in the array.

7 has a larger value.

 

Example 3 :

Input : nums = [-10,8,6,7,-2,-3]

Output : -1

Explanation : There is no a single valid k, we return -1.

 

Constraints :

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• nums[i] != 0

---

주어진 문제는 정수 배열 nums에서 -k도 존재하는 가장 큰 양의 정수 k를 찾는 것입니다. 배열에 해당 조건을 만족하는 k가 없다면 -1을 반환해야 합니다. nums에는 0이 포함되지 않으며, 배열의 길이는 최대 1000입니다.

 

// 내가 첨에 썼던 코드 : 
 class Solution {
    public int findMaxK(int[] nums) {
        List<Integer> numsArr = new ArrayList<>();
        for (int num : nums) {
            numsArr.add(num);
        }
        List<Integer> validNums = new ArrayList<>();
        for (int i = 0; i < numsArr.size(); i++) {
            if (numsArr.contains(numsArr.get(i))) {
                validNums.add(numsArr.get(i));
            }
        }
        Collections.sort(validNums);
        return validNums.get(validNums.size() - 1);
    }
}

 

이 코드는 사실 맨 처음에 쓴 코드입니다. Collections.sort() 를 쓴 바람에 이미 시간 적인 면에서 타격이 있었습니다. 비효율적인 코드인 거죠. 그래도 단계별로 어떻게 짜인 코드인지 설명드리겠습니다 : 

1. nums 배열을 리스트로 변환 :
   • 주어진 nums 배열을 numsArr 리스트로 변환합니다.
   • 리스트는 배열과 동일한 요소를 갖습니다.
2. 유효한 숫자를 찾기 위한 반복문 :
   • numsArr 리스트를 순회하며 numsArr.get(i)가 리스트에 존재하는지를 확인합니다.
   • 현재 코드에서는 numsArr.contains(numsArr.get(i)) 조건이 항상 참이므로, 모든 숫자가 validNums 리스트에 추가됩니다.
   • 문제점: 이 부분은 항상 참이므로 유효한 숫자 필터링이 이루어지지 않습니다.
3. 정렬 후 최대값 반환 :
   • validNums 리스트를 오름차순으로 정렬합니다.
   • 리스트의 마지막 요소를 반환합니다. 이는 가장 큰 양수 k를 반환하는 것처럼 보이지만, 유효한 k를 찾는 과정이 없기 때문에 의미가 없습니다.
4. • 시간 복잡도 : O(n^2)
     • 리스트에서 contains 메서드는 O(n)의 시간 복잡도를 가지므로, 반복문 내에서 사용 시 O(n^2) 복잡도를 초래합니다.
     • 리스트를 정렬하는 데 O(n log n)의 시간이 추가로 필요합니다.
   • 공간 복잡도 : O(n)
     • 두 개의 리스트(numsArr와 validNums)를 사용하여 O(n) 공간을 사용합니다.

코드의 문제점 :

• 유효한 k 필터링 누락 : 코드의 핵심은 numsArr에 대해 -k가 존재하는 k만을 필터링해야 합니다. 하지만 현재 조건은 항상 참이므로 이 필터링이 제대로 이루어지지 않습니다.
• 불필요한 연산 : 배열을 리스트로 변환하고, 요소 존재를 다시 검사하는 과정은 불필요하게 비효율적입니다.
• 올바르지 않은 로직 : 최대값을 찾기 위해 모든 숫자를 validNums에 넣고 정렬하는 방식은 문제의 요구를 만족시키지 못합니다.
• 그리고 애초에 아예 테스트도 모두 통과치 못한 코드입니다.

그래서 이를 고치며 개선시킨 코드가 다음과 같습니다 : 

---

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findMaxK(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        int largestK = -1;

        // Set에 모든 숫자를 추가
        for (int num : nums) {
            numSet.add(num);
        }

        // 가장 큰 k 찾기
        for (int num : nums) {
            if (num > 0 && numSet.contains(-num)) {
                largestK = Math.max(largestK, num);
            }
        }

        return largestK;
    }
}

 

생각을 바꿔서 Set를 쓰기로 했습니다. 

1. Set 사용 : Set<Integer> numSet = new HashSet <>();를 사용하여 중복 없는 숫자 저장소로 활용합니다.
   • 모든 숫자를 한 번에 O(1) 시간에 추가할 수 있습니다.
2. 조건 확인 : if (num > 0 && numSet.contains(-num)) 조건을 통해 k와 -k가 모두 존재하는지 확인합니다.
   • num이 양수인 경우에만 -num을 찾도록 하여 최댓값을 구합니다.
3. 최댓값 갱신 : largestK = Math.max(largestK, num);를 통해 k가 발견되면 최댓값으로 갱신합니다.

• 시간 복잡도 : O(n)
  • nums 배열을 한 번 순회하면서 각 숫자를 Set에 추가 및 검사하므로 O(n)입니다.
• 공간 복잡도 : O(n)
  • 모든 요소를 저장하기 위해 O(n) 공간이 필요합니다. Set을 사용함으로써 중복 없이 효율적으로 저장합니다.

---

이래도 제 코드가 Beats 100%가 안 뜨길래 궁금해서 다른 유저들 코드들을 확인해봤습니다.

 

이 분의 코드는 저보다 그래도 나은 코드인데요, 함께 보시겠습니다 : 

class Solution {
    public int findMaxK(int[] nums) {
        int [] positive=new int [1001];
        int [] negative=new int [1001];
        int ans=-1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                positive[nums[i]]++;
                if(negative[nums[i]]>0){
                    ans=Math.max(ans,nums[i]);
                }
            }
            else{
                negative[Math.abs(nums[i])]++;
                if(positive[Math.abs(nums[i])]>0){
                    ans=Math.max(ans,-nums[i]);
                }
            }
        }
        return ans;
    }
}
// Abhishekkant135 유저의 코드

 

이 코드를 보고 이 분은 약간 고수임을 눈치챘습니다. 저 배열의 길이 보세요, 1001 뭔가 웅장합니다.

이 분의 설명을 보고 이해했습니다. 제가 번역해 드리겠습니다 : 

1. 양수 및 음수 배열 초기화 :
   • int[] positive = new int[1001]; 배열을 사용하여 양수의 빈도를 저장합니다. 각 인덱스는 해당 숫자의 빈도를 나타냅니다.
   • int[] negative = new int[1001]; 배열을 사용하여 음수의 빈도를 저장합니다. 음수의 절댓값을 인덱스로 사용합니다.
2. 배열 순회 :
   • 주어진 nums 배열을 한 번 순회하여 각 요소를 확인합니다.
   • 양수일 경우 :
     • positive[num]++를 사용하여 양수 빈도를 증가시킵니다.
     • if (negative[num] > 0) 조건을 통해 해당 양수의 음수 값이 이미 존재하는지 확인합니다. 존재하면 ans를 갱신합니다.
   • 음수일 경우 :
     • negative[-num]++를 사용하여 음수의 절댓값에 해당하는 인덱스의 빈도를 증가시킵니다.
     • if (positive[-num] > 0) 조건을 통해 해당 음수의 양수 값이 이미 존재하는지 확인합니다. 존재하면 ans를 갱신합니다.
3. 최종 결과 반환 :
   • 모든 요소를 확인한 후, ans에 저장된 가장 큰 k를 반환합니다. 유효한 k가 없으면 -1을 반환합니다.

• 시간 복잡도 : O(n)
  • nums 배열을 한 번 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 nums의 길이입니다.
  • 각 숫자에 대해 배열에서의 조회 및 갱신은 O(1)입니다.
• 공간 복잡도 : O(1)
  • 추가적인 배열 positive와 negative는 크기가 고정되어 있으므로, 입력 크기에 상관없이 상수 공간을 차지합니다.
  • 따라서 공간 복잡도는 O(1)입니다.

---

내 코드와 다른 유저 코드 Runtime 결과