[Programmers]#Level2_뒤에 있는 큰 수 찾기, 스택

 

[Programmers 알고리즘, C++]#Level 2_뒤에 있는 큰 수 찾기

 

Programmers 알고리즘 문제 풀이, Level 2_뒤에 있는 큰 수 찾기

스택을 활용해 오른쪽에 있으며 가장 가까운 수 찾기

 

---

 

#1. 문제

 

 

#2. 풀이

1. 스택

[Basic C++] #64_stack

 

Details

 

• C++의 STL이 제공하는 stack 컨테이너입니다.
• 스택은 LIFO(Last-In First-Out)으로 동작하는 선형 자료구조입니다. 스택은 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 삽입/제거가 가능하고, "top()"메서드를 통해 가장 마지막으로 삽입된 항목만 접근이 가능합니다.

 

2. 스택의 오름차순 정렬

// 17298번 링크

1. 먼저, 이 문제를 해결하기 위해 우리는 배열을 역순으로 두어 생각합니다.
2. stack이 비어있지 않고, 현재 위치의 원소가 stack.top() 보다 작을 때까지 pop()을 수행합니다. 이를 통해, stack에 저장된 항목들이 Top -> Bottom 순서로 오름차순 정렬을 유지할 수 있습니다. 왜냐하면, s.top()이 현재 위치의 값보다 작다면, 다음 위치의 원소가 찾고있는 "뒤 큰 수"는 절대 s.top()이 될 수 없기 때문입니다. 우선, 현재 위치보다 s.top()의 위치가 다음 위치보다 멀고, 현재 위치의 값이 s.top() 보다 크다면, 다음 위치의 원소는 당연하게도 s.top()과 비교작업을 수행할 이유가 전혀 없기 때문이죠.
3. 위 작업을 수행하고, stack이 비어있다면, 현재 위치의 원소보다 오른쪽에 위치한 값들 중 해당 값보다 큰 값은 없다고 확신할 수 있습니다.
4. 위 작업을 수행하고, stack이 비어있지 않다면, 현재 위치의 원소보다 오른쪽에 위치한 값들 중 해당 값보다 크며, 가장 가까이에 있는 값이 stack.top()이라고 확신할 수 있죠.
5. 위 작업을 모두 수행하고, 마지막에 현재 위치의 원소를 stack에 push()하고 다음 원소로 위치를 이동합니다.

 

#3. 코드

 

/*
*   [문제]  : 현재 위치의 원소보다 오른쪽에 위치하며, 더 큰 수를 찾는 문제
*
*   [설명]  : BOJ_17298 문제와 동일한 문제, 배열을 역순회하며 stack을 오름차순 유지하며 top과 비교하는 문제
*/

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    stack<int> s;

    answer.resize(numbers.size(), -1);
    
    for(int i= numbers.size()-1; i>= 0; i--)
    {
        while(!s.empty() && numbers[i] >= s.top())
        {
            s.pop();
        }
        
        if(!s.empty()) 
            answer[i] = s.top();
        
        s.push(numbers[i]);
    }
    
    return answer;
}