CSES 2. Nearest Smaller Values (1645)

출처: https://cses.fi/problemset/task/1645

---

문제 설명

Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.

입력 

The first input line has an integer n: the size of the array.

The second line has n integers x_1,x_2,…,x_n: the array values.

출력

Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.

입력 예

8
2 5 1 4 8 3 2 5

출력 예

0 1 0 3 4 3 3 7

제약조건

• 1 <= n <= 2x10^5 
• 1 <= x_i <= 10^9

---

문제 풀이 내용

stack에 작은 값의 위치를 기록한다. 기록된 작은 값의 위치의 값과 새로운 입력을 비교해서 작으면 위치를 출력한다. 새로운 입력의 값이 가장 지금까지 입력중에 가장 작으면 0, 아니면 기록하는 위치를 갱신한다. 출력하는 값은 배열 값이 아니라, 배열 위치이므로 출력할때는 +1을 해준다.

프로그램 내용

...
    vector <long> in_num;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        in_num.push_back(temp);

    stack<int, vector<int>> num_stack;

    for(int idx = 0 ; idx < nNum; ++idx) 
        while(!num_stack.empty() && in_num[num_stack.top()] >= in_num[idx]) 
            num_stack.pop();

        if(num_stack.empty()) 
            cout << "0 " ; 
        else 
            cout << num_stack.top()+1 << " ";

        num_stack.push(idx);
...

 

Sorting and Searching ( link )