[stack][Medium] 739. Daily Temperatures

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

 

정수배열이 주어지고, 이 배열이 각 날짜의 온도를 의미한다.

각 날짜에서 더 따뜻해지는 날까지의 차수를 반환하라.

 

좋은 문제다. 

 

코드로 가기 전에 반드시 수기로 로직을 확인할 필요가 있겠다. 

stack 데이터로 온도와 index데이터를 가진다. 

현재 온도가 stack데이터 보다 높다면, 바로 계산하고 stack에 저장된 index에 이 차이를 쓴다.

낮다면, stack에 계속 저장한다. 

이게 다다. 

 

stack에 최소값을 순차적으로 넣고 특정 조건에 pop하면 이전 조건들을 그대로 이용할 수 있음을 활용한다.

 

코드 

vector<int> dailyTemperatures(vector<int>& temp) 
{    
    stack<pair<int, int>> sBuff;    // value, index
    vector<int> vRet;
    vRet.resize(temp.size(), 0);
    for (int q = 0; q < temp.size(); ++q)
    {
        while (sBuff.size() > 0)
        {
            auto pair_data = sBuff.top();

            if (temp[q] > pair_data.first)
            {
                sBuff.pop();
                vRet[pair_data.second] = q - pair_data.second;
            }
            else break;
        }
        sBuff.push(make_pair(temp[q], q));
    }
    return vRet;
}

 

결과.