[2024] day 124. Leetcode 2441. Largest Positive Integer That Exists With Its Negative

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 2일 (목)
Leetcode daily problem

2441. Largest Positive Integer That Exists With Its Negative

https://leetcode.com/problems/largest-positive-integer-that-exists-with-its-negative/?envType=daily-question&envId=2024-05-02

Problem

Solution

set, array

처음 생각했던 아이디어는 배열을 탐색하면서 해당 원소의 부호를 바꾸고, 배열 내에 바꾼 원소가 존재한다면 조건에 맞기 때문에 최대값을 업데이트 하는 식으로 풀었다. 해당 코드는 그러나 공간복잡도는 O(1)이지만 시간복잡도가 O(n^2)이 소요된다.

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        
        ans = -1
        for n in nums:
            if n*(-1) in nums:
                ans = max(ans, abs(n))
        
        return ans
                
        

(leetcode 정규표현식에서도 거의 우측 꼬리에 있음 꼬리칸임 아주 그냥)

더 효율적인 풀이를 생각해보면 배열을 한 번만 탐색해서 해당 문제를 풀어야 한다.

배열을 한 번만 도는데, 배열을 돌 때 현재 위치에서 해당하는 원소를 배열의 요소를 set에 저장하면서 처음 -1로 초기화해놨던 최종 ans 보다 큰지, 또한 set에 저장되어있는 원소 인지 (부호만 다른 동일한 값이 들어왔는지 아닌지 체크 하는 것) 확인한후 최종 ans를 업데이트 한다.

이 경우 배열을 한 번만 순환하기 때문에 좀 더 효율적으로 문제를 해결할 수 있다.

Code

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        ans = -1
        visited = set()
        
        
        for num in nums:
            if ans < abs(num) and -num in visited:
                ans = abs(num)
            
            visited.add(num)
            
        return ans
            

Complexicity

시간 복잡도

주어진 배열을 한 번 탐색하므로 시간 복잡도는 O(n)이다.

공간 복잡도

배열을 탐색하면서 해당 원소들을 저장하므로 공간 복잡도는 O(n)이다.