[Algorithm] Programmers :: 뒤에 있는 큰 수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

vector<int> solution(vector<int> numbers)
{
    vector<int> answer(numbers.size());
    stack<int> s;
 
    for (int i = numbers.size() - 1; i >= 0; --i)
    {
        while (1)
        {
            if (s.empty())
            {
                answer[i] = -1;
                break;
            }
 
            if (s.top() > numbers[i])
            {
                answer[i] = s.top();
                break;
            }
 
            s.pop();
        }
        s.push(numbers[i]);
    }
    
    return answer;
}

 

이런 문제도 몇개 풀면서 느낀건데... 대충 문제설명 읽으면 뒤에서부터 값을 저장하면서 0으로 다가가야한다는걸 바로 알기는 한다.. 다만 이번문제같은 경우는 결국 다른사람 풀이를 참고했다.

시간효율을 너무 좋게하는 방법을 우선으로 생각하다보니 오히려 문제를 못풀어버리는 것 같다.

 

로직은 매우 간단하다. numbers의 끝에서부터 0번째 인덱스까지 접근할건데, 매 시도마다 스택에 numbers[i]값을 계속 넣어주는걸 전제로 한다.

그리고 스택의 값들을 검사할건데, 자기보다 큰값이 나올때까지 그냥 pop을 해버린다.

매번 계속 스택에 넣긴 하기때문에, 스택의 top에는 가장 가까운 인덱스의 값이 들어있기 때문에 가능하니 로직이다.

 

원하는 값(자신보다 큰 값)을 찾으면 answer[i]에 기록하고 반복문을 탈출한다음, stack에 자기값(numbers[i])를 넣고 다음 인덱스로 넘어가면 된다.