[Leetcode] Daily Temperatures 풀어보기

https://leetcode.com/problems/daily-temperatures/description/?utm_source=chatgpt.com

Daily Temperatures - LeetCode

 

이번 문제는 Monotonic Stack을 사용하는 문제입니다.

 

기본적으로는 현재 위치의 원소의 값보다 큰 값 중 가장 가까운 위치를 찾는 문제입니다.

가장 먼저 생각날만한 것은 O(n^2)으로 순회한다면 바로 해결할 수 있을 것입니다.

 

다만 다른 방법도 생각해볼만합니다. 만약 배열 끝에서부터 순회하며 갱신해나간다면, 해당 위치에서 가장 가까운 답을 찾을 수 있을 것입니다. 

자세한 설명은 아래 링크를 확인해주세요

 

https://www.geeksforgeeks.org/dsa/introduction-to-monotonic-stack-2/

Introduction to Monotonic Stack - GeeksforGeeks

 

 

---

아래는 제가 작성한 코드입니다.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int size = temperatures.size();
        vector<int> answer(size, 0);
        stack<pair<int, int>> stk;

        for (int i = size - 1; i >= 0; --i)
        {
            int target = temperatures[i];
            if (stk.empty())
            {
                stk.push({target, i});
            }
            else
            {
                while (!stk.empty())
                {
                    auto [v, idx] = stk.top();
                    if (target <= v)
                    {
                        stk.push({ target, i });
                        answer[i] = idx - i;
                        break;
                    }
                    else
                    {
                        stk.pop();
                    }
                }
                if (stk.empty())
                {
                    stk.push({ target, i });
                }
            }
        }
        return answer;
    }
};

---

2번방법

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int size = temperatures.size();

        vector<int> answer(size, 0);
        stack<int> stk;

        for (int i = size - 1; i >= 0; --i)
        {
            while (!stk.empty() &&
                   temperatures[stk.top()] <= temperatures[i])
            {
                stk.pop();
            }

            if (!stk.empty())
            {
                answer[i] = stk.top() - i;
            }

            stk.push(i);
        }

        return answer;
    }
};

---

3번 방법

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int size = temperatures.size();

        vector<int> answer(size, 0);
        vector<int> stk;
        stk.reserve(size);

        for (int i = size - 1; i >= 0; --i)
        {
            while (!stk.empty() &&
                   temperatures[stk.back()] <= temperatures[i])
            {
                stk.pop_back();
            }

            if (!stk.empty())
            {
                answer[i] = stk.back() - i;
            }

            stk.push_back(i);
        }

        return answer;
    }
};

---

2번과 3번은 방법자체는 1과 동일하지만 최적화를 한 코드입니다.

 

처음에 만들 때 복잡했던 분기를 줄이고, stack자체가  push pop에 시간이 들어가기 때문에 CPU cache에 대한 hit율이 높은 vector로 대체해 구현해 시간을 줄였습니다.