LeetCode [496]: Next Greater Element I

📌 LeetCode [496]: Next Greater Element I

🔗 문제 링크

---

문제 설명 📄

nums1과 nums2가 주어졌을 때, nums1의 각 원소에 대해 nums2에서 그 원소보다 큰 첫 번째 값을 찾습니다. 만약 찾을 수 없다면 -1을 반환합니다.

---

문제 해결 접근 🧩

1. OrderedDict 사용:
   • nums1의 요소를 키로, 값을 -1로 초기화하여 저장.
2. 중첩 반복:
   • nums2의 각 요소에 대해 오른쪽으로 이동하며 다음으로 큰 값을 탐색.
3. 결과 반환:
   • nums1의 순서를 유지한 결과를 반환.

---

Solution 💻

from collections import OrderedDict

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        pattern = OrderedDict([i, -1] for i in nums1)

        for i in range(len(nums2) - 1):
            for j in range(i + 1, len(nums2)):
                if nums2[i] < nums2[j]:
                    if nums2[i] in pattern:
                        pattern[nums2[i]] = nums2[j]
                    break

        return list(pattern.values())

시간 복잡도 분석 ⏲️

• 중첩 반복문: O(m * n) (m은 nums2의 길이, n은 nums1의 길이).
• 결과 생성: O(n) (n은 nums1의 길이).
• 최종 시간 복잡도: O(m * n).

공간 복잡도 분석 🗄️

• OrderedDict 사용 공간: O(n) (n은 nums1의 길이).
• 총 공간 복잡도: O(n).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        next_greater = {}

        for num in nums2:
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)

        return [next_greater.get(num, -1) for num in nums1]

리팩토링 후 시간 복잡도 ⏲️

• 단일 반복: O(m + n) (m은 nums2의 길이, n은 nums1의 길이).
• 결과 생성: O(n).

리팩토링 후 공간 복잡도 🗄️

• 스택 및 딕셔너리 공간: O(m).

---