[Leetcode]#496. Next Greater Element I

문제 : 

 

예시 :

 

 

문제는 보기보다 간단하다. 두개의 배열이 파라미터로 주어지고, nums1을 순회하며 nums1[i]보다 큰 값이 nums2[j]의 "오른쪽" 에 있는지 확인하고, 있다면, 결과 리스트에 값을 추가하고, 없다면 -1을 추가한다. 

 

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans =[]
        for i in range(len(nums1)):
            idx = nums2.index(nums1[i])
            found = False
            for j in range(idx + 1, len(nums2)):
                if(nums1[i] < nums2[j]):
                    ans.append(nums2[j])
                    found = True
                    break
            if not found:
                ans.append(-1)
        return ans

 

- 먼저, 결과값들을 담을 배열 ans를 선언한다.

- 우리의 목적은 nums1에 있는 값들보다 큰 값을 찾아야 하므로, nums1은 무조건 처음부터 끝까지 순회해야 한다.

- 이 문제는 정렬을 할 수도없고, nums1[i]보다 큰 값을 찾기 위해 배열의 처음부터 검색 할 수 없었다. 문제의 조건을 다시 읽어보면 왜 그런지 알 것이다.

- 그래서 idx라는 변수를 선언해 nums1[i]는 nums[j]의 몇번째 인덱스에 있는지 저장한다. 

- 그 인덱스를 찾으면, 그 인덱스 이전의 값은 nums[i]보다 크던 말던 검사 할 필요가 없다. 또한, 우리는 nums2배열의 특정 값의 오른쪽에서만 값이 큰지 아닌지만 확인하면 되므로, 불필요한 검사 1회를 줄이기 위해 idx + 1을 해 주었다.

- 조건을 검사하고, 조건에 부합하면 .append를 이용해 결과 리스트에 값을 담아준다. 그리고 그 다음 요소들은 더 큰 값이 있던 말던 우리는 더 큰 값 하나만 찾으면 되므로 break를 통해 for문을 빠져 나온다.

-마지막으로, 위에서 선언한 found라는 변수를 확인해주고, 만약 배열의 끝까지 도달하더라도 찾지 못했다면 -1을 더해준다.

 

아래는 내가 받은 report이다.

 

현재 코드의 시간 복잡도는 nums1의 각 요소에 대해 nums2를 반복해서 검색하기 때문에 O(n * m)이다. 여기서 n은 nums1의 길이, m은 nums2의 길이이다.

 

여기서 난 어떠한 자료구조도 사용하지 않고 brute force를 사용해 풀었지만, 이 문제는 stack을 활용해도 쉽게 풀릴 문제였다. 스택을 사용한 방법의 시간 복잡도는 O(n + m)이다.

 

다음은 solution에서 가져온 최적화된 코드이다.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater = {}
        stack = []
        
        # Iterate through nums2 to find the next greater elements
        for num in nums2:
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)
        
        # Use the next_greater dictionary to build the result for nums1
        ans = [next_greater.get(num, -1) for num in nums1]
        
        return ans

 

- nums2를 순회하며 스택을 사용해 각 요소의 다음 큰 요소를 찾는다.

- while stack은 stack에 요소가 남아있는동안 실행된다. 

- stack[-1] < num은 stack의 맨 위에 있는 요소가 num보다 작을동안 실행된다.
-스택의 상단에 있는 요소가 현재 요소보다 작으면, 스택에서 제거하고 그 요소의 다음 큰 요소로 현재 요소를 저장한다.
-nums2를 다 순회한 후, next_greater 딕셔너리에 각 요소의 다음 큰 요소가 저장된다.
-nums1의 각 요소에 대해 next_greater 딕셔너리에서 값을 찾아 결과 리스트를 만든다.

 

현재 코드의 시간 복잡도가 비효율적인 이유와 개선된 코드가 더 효율적인 이유는 다음과 같다:

현재 코드의 시간 복잡도
현재 코드는 `nums1`의 각 요소에 대해 `nums2`에서 해당 요소를 찾고, 그 다음에 다음 큰 요소를 찾기 위해 `nums2`의 나머지 부분을 탐색한다. 구체적으로는:

1. `nums1`의 각 요소에 대해 `nums2.index(nums1[i])`를 호출한다. 이 연산은 최악의 경우 O(m) 시간이 걸린다.
2. 그 다음, `nums2`의 나머지 요소를 탐색하여 다음 큰 요소를 찾는다. 이 또한 최악의 경우 O(m) 시간이 걸린다.

따라서 전체 시간 복잡도는 O(n * m)이다. 여기서 `n`은 `nums1`의 길이, `m`은 `nums2`의 길이이다.

최적화된 코드의 시간 복잡도
최적화된 코드는 스택을 사용하여 다음 큰 요소를 찾는다. 이 방법은 각 요소를 한 번씩만 처리하므로 시간 복잡도가 개선된다:

1. `nums2`를 한 번 순회하며 스택을 사용하여 다음 큰 요소를 찾는다. 각 요소는 스택에 한 번 추가되고, 한 번 제거된다. 이 과정은 O(m) 시간이 걸린다.
2. `nums1`의 각 요소에 대해 `next_greater` 딕셔너리에서 값을 조회한다. 딕셔너리 조회는 평균적으로 O(1) 시간이 걸리므로, 이 과정은 O(n) 시간이 걸린다.

따라서 전체 시간 복잡도는 O(m + n)이다.

왜 최적화된 코드가 더 효율적인가?
최적화된 코드는 각 요소를 한 번씩만 처리하고, 다음 큰 요소를 찾기 위해 스택을 사용한다. 이 방법은 요소를 중복해서 탐색하지 않기 때문에 시간 복잡도가 개선된다. `nums1`과 `nums2`의 길이가 클수록 이 차이는 더욱 두드러진다.