문제

문제 링크

해설

• N이 100만이므로 O(N²)으로 절대 풀 수 없고 최소한 O(N×logN)으로 풀어야 합니다.

• arr[5] = 3 8 2 7 9 이라는 예를 생각해봅시다.

  • 처음에는 ans 배열을 -1 -1 -1 -1 -1 로 초기화합니다.
  • 뒤에서부터 생각해봅시다. 9는 당연히 맨 끝 요소이므로 ans[4] -1 그대로 놔둡니다.
  • arr[3] = 7 은 arr[4]인 9보다 작기 때문에 ans[3]은 9가 됩니다.
  • arr[2] = 2 는 arr[3]인 7보다 작기 때문에 ans[2]는 7이 됩니다.
  • arr[1] = 8 은 arr[2]인 2와 ans[2]인 7과 비교했을 때 양쪽 모두보다 큽니다.

• 바로 이렇게 arr 배열의 다음 수와 ans 배열의 다음 수 양쪽 모두보다 클 경우가 가장 까다롭습니다.

• 따라서 여기서 ‘아, 단순히 인접한 배열끼리 비교해서는 안 되는구나’ 라는 점을 깨달아야 합니다.

• 그러므로 스택(stack)을 사용하는 아이디어를 떠올리면 100점입니다.

  • 스택에 값을 넣을 때는 {값, 인덱스번호}의 pair를 넣습니다.
  • 스택에 넣을 값보다 작은 값들은 모두 pop한 뒤 ans[] 배열에 현재 넣을 값을 넣습니다.

코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int N;
    cin >> N;

    stack<pair<int, int>> stk;
    vector<int> answer(N, -1);
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        if (stk.empty() || stk.top().first > num) {
            stk.emplace(num, i);
            continue;
        }
        while (!stk.empty() && stk.top().first < num) {
            answer[stk.top().second] = num;
            stk.pop();
        }
        stk.emplace(num, i);
    }
    for (auto i : answer) cout << i << ' ';
    return 0;
}

소스코드 링크

결과