https://school.programmers.co.kr/learn/courses/30/lessons/154539
더보기
앞에서부터 각 원소에 대해 차례대로 루프를 돌며 자신보다 큰 뒤의 수를 찾게 되면, 최악의 경우 O(n^2)의 시간 복잡도가 발생하게된다.
n 값이 매우 커서 어떻게 접근해야할지 한참을 고민하다가 자신보다 뒤에 큰 수를 구하는 것이기에 뒤에서 부터 탐색하면 어떨지 생각해보게 되었고, 현재 탐색하는 원소 보다 이전에 큰 수가 있었는지 확인하기 위해, 이전에 탐색한 큰 수를 저장할 컨테이너로 stack을 활용해보도록 했다.
✅ 구현 코드
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> numbers)
{
int n = numbers.size();
vector<int> answer(n, -1);
stack<int> st;
// 뒤에서부터 순회
for (int i = n - 1; i >= 0; --i)
{
// stack에 현재 탐색하는 원소보다 큰 값만 남기고 전부 삭제
while (!st.empty() && numbers[i] >= st.top())
{
st.pop();
}
// 탐색하는 현재 원소보다 뒤 원소가 더 크다면 answer에 stack의 값 추가
if (!st.empty())
{
answer[i] = st.top();
}
// 뒤에서부터 모든 원소는 stack에 저장
st.push(numbers[i]);
}
return answer;
}
1️⃣뒤에서 부터 순회하며 각 원소들을 stack에 저장
2️⃣stack이 비어있지 않았을 때, stack의 top 원소가 numbers[i]보다 큰 값을 제외하고 모두 제거
3️⃣numbers[i]보다 stack의 top 원소가 더 크다면, 그 값이 해당 인덱스 자리에서 뒤에 오는 큰 수를 의미
4️⃣이 로직을 numbers의 첫 번째 인덱스까지 반복하면, answer 배열의 각 인덱스 자리에 다음에 오는 큰 수가 저장됨
'공부 > Code Cata' 카테고리의 다른 글
숫자 변환(BFS) (0) | 2025.04.11 |
---|---|
롤케이크 자르기 (0) | 2025.04.01 |
스타트와 링크 문제 / 백트래킹 (0) | 2025.03.20 |
주차 요금 계산 문제 (0) | 2025.03.20 |
k진수에서 소수 개수 구하기 (0) | 2025.03.19 |