🟢[Leet code - 496] Next Greater Element I ✅

Next Greater Element I - LeetCode

문제

• Input
  정수배열 nums1, nums2
• Output
  정수배열 answer
  answer[i] = nums1[i] == nums2[j] 일때, nums2[j]의 Next Greater Element
  ※ Next Greater Element : 오른쪽에 등장하는 원소중 가장 가깝고 더 큰 값을 가진 원소
• Constraints
  nums1과 nums2에 포함된 모든 정수는 서로 다르다.
  nums1은 nums2의 부분집합이다.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관 없음 | O(log n) : 크게  상관 없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$1 \le nums1.size \le nums2.size \le 1'000$ 이므로 $O(n^2)$부터 고려해볼 수 있다.

 

 

해결 과정

가장 먼저 떠오른 방법은 완전탐색으로, nums1의 각 원소마다 nums2를 순회하여 같은 값을 찾고,
그 뒤에서 처음으로 더 큰 값을 다시 찾는 방식이다.

하지만 이 방법은 nums1의 각 원소마다 이미 검사했었던 nums2의 원소를 반복해서 보게 되므로 비효율적이라고 생각했다.

여기서 어떻게 최적화를 할 수 있을까 고민했고, 현재 값을 확인하는 순간 이전의 미해결 원소들을 한 번에 해결할 수 있다고 생각하여, 해당 문제에 어울리는 스택을 고려해보기로 했다.

근데 이 문제는 nums2의 모든 원소에 대한 답이 필요한 것이 아니라, nums1에 포함된 값들에 대한 답만 필요하기 때문에,
그래서 먼저 nums1의 속한 값을 빠르게 찾을 수 있도록, 값을 key, nums1에서의 인덱스를 value로 하는 map을 사용하여 저장하기로 했다.

이후 nums2를 왼쪽부터 순회하면서, 아직 next greater element를 찾지 못한 원소들을 스택에 저장한다.
현재 값 nums2[i]가 스택 top의 값보다 크다면, 스택 top 원소의 next greater element는 nums2[i]로 확정할 수 있다.

 

정답 배열의 위치가 nums1 기준이므로, 스택에서 꺼낸 값이 nums1에 있는지, 있다면 몇 번째 원소인지 map으로 찾은 뒤 그 위치에 정답을 기록하면 된다.

 

구현

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 
{
    unordered_map<int, int> check;
    for (int i = 0 ; i < nums1.size(); ++i)
    {
        check.insert({nums1[i], i});
    }

    vector<int> ans(nums1.size(), -1);
    stack<int> s;

    for (int i = 0 ; i < nums2.size(); ++i)
    {
        while (s.empty() == false && nums2[s.top()] < nums2[i])
        {
            ans[check[nums2[s.top()]]] = nums2[i];
            s.pop();
        }

        if (check.find(nums2[i]) == check.end()) continue;
        s.push(i);
    }

    return ans;
}

 

 

개선 코드

스택에 nums1의 인덱스를 저장하는 바람에 좀 더 복잡하게 생각하게 되어 시간이 많이 소요됐었다..

아래와 같이 값을 저장하는게 훨씬 빠르고 편하다.

for (int i = 0 ; i < nums2.size(); ++i)
{
    while (s.empty() == false && s.top() < nums2[i])
    {
        ans[check[s.top()]] = nums2[i];
        s.pop();
    }

    if (check.find(nums2[i]) == check.end()) continue;
    s.push(nums2[i]);
}