문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

• 랜덤한 정수 배열이 주어진다.
  • 각 원소는 1 <= x <= 1,000,000
  • 배열의 길이는 4 <= len <= 1,000,000
• 자기 자신보다 뒤에 잇는 숫자 중 자신보다 크면서 가장 가까이 있는 수를 찾아라
  • 없다면 -1로 채운다.
• 예시
  • [1,2,2,3] -> [2,3,3,-1]

2. 알고리즘 설계

• 나중에 들어간 게 먼저 나와야 하므로, stack 이용
• pair<int, int>로 값과 index를 저장해둬야 한다.
  • index를 저장하는 이유는 아래에서 설명

3. 로직

• 현재 값이 이전 값보다 작으면, 더 볼 필요가 없다.
• 아니라면, 값을 계속 덮어쓴다.
  • if 조건에 걸릴 때까지 계속해서 큰 값으로 덮어써진다.

  while (!st.empty()) 
  {
      pii cur = st.top()
    
      // numbers[i-n] >= numbers[i]
      if (cur.first >= numbers[i])
          break;
        
      // if not, update
      ans[cur.second] = numbers[i];
      st.pop();
  }
  

4. 전체 코드

#include <vector>
#include <stack>

using namespace std;
using pii = pair<int, int>;

vector<int> solution(vector<int> numbers) {
    int sz = numbers.size();
    vector<int> ans(sz, -1);

    stack<pii> st;
    for (int i = 0; i < sz; i++) {
        while (!st.empty()) {
            pii cur = st.top();

            if (cur.first >= numbers[i])
                break;
            
            ans[cur.second] = numbers[i];
            st.pop();
        }
        st.push({ numbers[i], i });
    }
    return ans;
}

5. 소감

• 처음 내 코드는 조금 더 지저분했다.
• 하나의 스택과 for문 한줄로 처리가 가능한 풀이가 있어 참고하였다.
• 값과, index를 이용한 매우 아름다운 코드인 거 같다…