[BOJ알고리즘, C++]#17298_오큰수, 스택

 

[BOJ알고리즘, C++]#17298_오 큰 수

 

BOJ 알고리즘 문제 풀이, 17298번 문제 "오 큰 수"

C++의 STL이 제공하는 stack 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 스택

[자료 구조]#0_선형 자료구조

 

[Basic C++] #64_stack

 

Details

 

• 스택은 LIFO(후입선출) 방식으로 동작하는 선형 자료구조입니다.
• 스택은 같은 구조와 같은 크기의 데이터를 정해진 한 방향으로만 삽입/삭제가 가능한 자료구조입니다.

 

2. 스택의 오름차순 정렬

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

 

1. 우리는 주어진 배열에서 현재 위치의 값보다 오른쪽에 위치한 항목들 중 현재 위치의 원소보다 크며 가장 가까이에 위치한, 혹은 가장 왼쪽에 위치한 원소를 찾아야 합니다.
2. 먼저, 주어진 배열을 역순으로 순회하며 항목들을 차례대로 stack에 삽입합니다. 이렇게 되면, 이미 stack에 저장된 값들은 배열의 현재 위치의 값보다 오른쪽에 위치한 값들이며, stack의 Top -> Bottom 순서로 현재 위치의 값과 가까운 값들로 이루어집니다.
3. 다음으로, 현재 위치의 값과 stack의 top을 비교하여, 현재 위치의 값이 stack의 top보다 크다면, stack의 top을 제거합니다(pop 수행). 이유는 간단합니다. 현재 위치의 값을 'A'로 가정하고, 현재  stack의 top 값을 'B', 그리고 배열의 다음 위치의 값을 'C'라고 가정합니다. A > B, 그리고 C > A 라면, 당연히 C > B입니다. 말 그대로, 배열의 현재 위치의 값이 stack의 top 값보다 크다면, 자동적으로 배열의 다음 위치의 "오큰수"는 배열의 현재 위치의 값이 되기 때문입니다. 따라서, 현재 stack의 top 값은 stack에 남아있을 이유가 없게 됩니다
4. 위 작업을 모두 마치고 stack에 남아있는 top 값이 현재 위치 원소의 "오 큰 수"가 됩니다. 만약, stack에 남아 있는 값이 없을 경우, 현재 위치 원소의 "오 큰 수"는 없습니다.
5. 마지막으로, stack에 현재 위치의 원소를 push 하고 다음 위치로 이동합니다.

 

#3. 코드

 

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    stack<int> s;
    
    cin >> N;
    
    vector<int> seq(N);
    vector<int> ans(N);
    
    for(int i=0; i<N; i++)
    {
        cin >> seq[i];
    }
    
    for(int i=N-1; i >= 0; i--)
    {
        while(!s.empty() && seq[i] >= s.top())
            s.pop();
        
        if(s.empty()) ans[i] = -1;
        else ans[i] = s.top();
        
        s.push(seq[i]);
    }
    
    for(int i=0; i<ans.size(); i++)
        cout << ans[i] << ' ';
    
    return 0;
    
}