뒤에 있는 큰 수 찾기 / stack

2025. 3. 25. 10:17·공부/Code Cata

 

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
'공부/Code Cata' 카테고리의 다른 글
  • 숫자 변환(BFS)
  • 롤케이크 자르기
  • 스타트와 링크 문제 / 백트래킹
  • 주차 요금 계산 문제
동그래님
동그래님
  • 동그래님
    개발자 동그래
    동그래님
  • 전체
    오늘
    어제
    • 분류 전체보기 (210)
      • 공부 (51)
        • Code Cata (50)
      • 내배캠 (151)
        • TIL (50)
        • C++ (37)
        • Unreal Engine (48)
        • GAS(Gameplay Ability System.. (16)
      • Project (7)
        • Gunfire Paragon (5)
        • Arena Fighters (1)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    동그래님
    뒤에 있는 큰 수 찾기 / stack
    상단으로

    티스토리툴바