[Leet code - 739] Daily Temperatures ✅

문제

Input : 정수 배열 n

Output[ i ] : n[i] 이후의 값 중 더 큰 수가 나오기까지의 index차이, 없다면 0으로 저장

 

 

시간 복잡도

$1 <= n <= 100'000$ 

• $n^2 = 10'000'000'000$ ❌
• $n \log{n} = 1'700'000$ ✅

n log n 부터 고려해 볼 수 있다.

 

해결 계획

처음에 $n^2$인 2차 반복문밖에 생각이 안 났어서 꽤나 고민했다.

이것저것 생각하다가 어쩌다보니 스택을 생각하였는데 좋은 아이디어였다.

 

대략 구성한 로직은 이렇다.

vector<int> dailyTemperatures(vector<int>& input) {

    // first : value | second : index
    stack<pair<int,int>> stk;
    
    for (int i = 0 ; i < input.size(); ++i)
    {
        while ( /*스택이 비지 않았을 경우*/ && /*top이 자신보다 작을 경우*/)
        {
            //인덱스 차이 계산하고 결과에 삽입, pop을 해야함
        }
        
        //자기 자신 저장
    }

    // 남은 스택에 대하여는 0으로 저장
}

 

2중 반복문이지만 모든 원소를 pop 한 번, push 한 번 연산하기 때문에 2n으로 O(n)으로 볼 수 있다.

 

직접 값을 넣어서 테스트하면 이렇다.
n = [ 3, 5, 1, 6 ] 로 가정한다.

1. 스택이 없으므로 삽입
   stack : [3] | output : [-, -, -, -]
2. 5는 top인 3보다 크기 때문에 결과 계산하여 저장하고 pop후, 자신을 push
   stack : [5] | output : [1, -, -, -]
3. 1은 top보다 작기 때문에 자신만 push
   stack : [5, 1] output : [1, -, -, -]
4. 6은 이후에 나올 top보다 모두 크기 때문에, 차례대로 pop후, 자신을 push
   stack : [6] output : [1, 1, 2, -]
5. 순회 종료후, 스택에 남은 값들은 모두 0으로 저장
   stack : [] output : [1, 1, 2, 0]

이 방법은 스택이 항상 내림차순으로 정렬되어야 한다는 가정이 필요하다.
하지만 혹시 정렬이 깨지는 경우가 있지 않을까 생각했지만,
항상 자기보다 작은 값은 pop하기 때문에 정렬이 깨지는 일은 없다고 생각한다.

 

 

구현

vector<int> dailyTemperatures(vector<int>& n) {
    // first : value | second : index
    stack<pair<int,int>> stk;
    vector<int> result(n.size(), 0);
    
    for (int i = 0 ; i < n.size(); ++i)
    {
        while (!stk.empty() && stk.top().first < n[i])
        {
            // 결과 배열에 넣고
            result[stk.top().second] = i - stk.top().second;
            // pop을 해야함
            stk.pop();
        }
        
        //자기 자신 저장
        stk.push({n[i], i});
    }

    // 남은 스택에 대하여 결과 저장
    while(!stk.empty())
    {
        result[stk.top().second] = 0;
        stk.pop();
    }

    return result;
}

 

 

되돌아보기

Monotonic stack(단조 스택)

이번 문제의 풀이 접근 방법이

뭔가 이렇게 하면되겠다 ⇒ 이 방법은 스택이 딱이야!

이게 아니라

 

이것저것 하다가 스택으로는 가능한가? ⇒ 어 되네?

이었기 때문에 먼가 맘에 안 든다;

 

그래서 어떻게 접근해야 했을까 찾아보다가, 

일단 답을 못 찾은 애들은 보관했다가, 나중에 조건이 맞을 때 한꺼번에 처리할 수 있을까?

이런 질문의 답이 바로 스택이다.

 

물론 스택을 나도 알기 모르게 이렇게 사용하고 있었지만, 이렇게 구체적으로 생각해보지 않아서 접근하기 어려웠나 보다.

참고로 이렇게 스택 내부가 항상 오름차순, 내림차순을 유지하도록 강제하는 스택을 단조 스택이라고 한다고 한다.

 

vector 사용 실수

결과 벡터에 reserve만 하고 계속 index 접근을 하고 있었다...（；´д｀)

push_back을 할 게 아니라면 초기화로 꼭 접근하자.

 

 

개선 코드 

나는 pair를 저장했지만, 사실 index만 저장해도 가능하기에 보다 메모리 최적화를 할 수 있다.

// before
while (!stk.empty() && stk.top().first < n[i])
{
    result[stk.top().second] = i - stk.top().second;
    stk.pop();
}


// after
while (!stk.empty() && n[stk.top()] < n[i])
{
    result[stk.top()] = i - stk.top();
    stk.pop();
}