[LeetCode] C++ 739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/description/

 

문제

 

문제 분석

- 스택을 이용해서 온도와 index를 같이 저장해놓고, stack의 top과 현재 temperature를 비교해서 현재가 더 높은 경우에는 stack에서 제거한 뒤 result에 해당하는 index에 Index - 현재 index를 기록합니다. 현재 temperature가 더 높다면 계속 반복합니다.

 

풀이

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

        stack.emplace_back(temperatures[0], 0);

        for(int i = 1; i < temperatures.size(); ++i){
            while(!stack.empty() && stack.back().first < temperatures[i]){
                auto top = stack.back();
                stack.pop_back();
                result[top.second] = i - top.second;
            }
            stack.emplace_back(temperatures[i], i);
        }

        return result;
    }
};

vector를 사용한 이유

std::vector가 메모리를 연속적으로 관리하여 캐시 히트율이 높고, 불필요한 오버헤드가 적습니다. 반면 std::stack은 내부적으로std::deque를 사용하고, 더 복잡한 메모리 구조를 가지기 때문에 std::vector보다 약간 느릴 수 있습니다. 스택과 같은 단순한 구조에서는 std::vector를 스택처럼 사용하는 것이 성능 면에서 유리할 수 있습니다.