[Monotonic Stack][Medium] 739. Daily Tempreatures

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 배열은 각 날짜의 온도를 의미한다. 

각 날짜에서 해당 일보다 더 따뜻한 날을 만나기까지 기다려야 하는 날 수를 출력하라.

 

 

Solution.

  일단 2중 배열을 돌면 해결은 간단해 진다. 하지만 O(NxN)의 TC로 적당하지 않은 해결책이며 실제 결과도 그렇게 나온다. 

vector<int> dailyTemperatures(vector<int>& temp) 
{    
    vector<int> vRet;
    vRet.resize(temp.size(), 0);

    for (int k = 0; k < temp.size()-1; ++k)
    {
        for(int q = k+1; q < temp.size(); ++q)
        {
            if(temp[k] < temp[q])
            {
                vRet[k] = q - k;
                break;
            }
        }
    }
    return vRet;
}

 

 

 다음으로 생각해 보면, 한 날짜에서 더 온도가 높은 날을 만나면 그 차이를 구하고 그 data는 더이상 필요하지 않음을 알 수 있다. 즉, stack을 이용하면, stack의 top이 언제나 최소 온도가 되고 이를 이용하면 최소한의 연산이 가능해 진다.

(현재가 top 보다 작다면(cur <= top), 현재가 stack의 새로운 top이 될 것이고, - 최소값이 top으로 계속 유지, 

 그렇지 않고 현재가 더 따뜻하다면 (cur > top), top은 제거되며 잔여 stack 원소에 대해 조건을 반복한다. - stack을 비우거나 위 조건에 의해 멈추거나 - 따라서 새로운 현재가 다시 최소값이 된다.) 

또 이것을 새로운 current와 비교, 반복 한다.

 

 출력은 입력만큼의 int 버퍼가 필요하다. 

 stack은 값과 그 차이를 계산할 위치, 즉 index 값이 필요하다. 따라서 pair로 저장해야 옳다. 

 

 이를 코드로 옮겨 보자. 

 

vector<int> dailyTemperatures(vector<int>& temp)
{
    vector<int> vRet;
    vRet.resize(temp.size(), 0);

    // 문제 조건에서 1개 이상의 input이 들어오므로, 예외처리는 필요없다.
    //
    stack<pair<int, int>> sBuff;
    sBuff.push(make_pair(temp[0], 0));

    for (int k = 1; k < temp.size(); ++k)
    {
        int curTemp = temp[k];
        // 2중 for loop로 보이지만, 
        // 원소를 1번씩만 더 check하므로 N+1 정도, 즉, 최종적으로 O(N)에 가깝게 된다.
        while (!sBuff.empty())
        {
            if (sBuff.top().first < curTemp)
            {
                // 기록해야 할 위치에 index 차이를 저장한다.
                vRet[sBuff.top().second] = k - sBuff.top().second;
                sBuff.pop();
            }
            else break;
        }
        sBuff.push(make_pair(curTemp, k));
    }
    // 조건에 불만족하는 잔여 date들은 0으로 초기화 하였으므로, 더 할 것이 없다.
    
    return vRet;
}

 

 

결과.