[백준] 17298 오큰수

2161 단어 백준백준

[백준] 17298 오큰수

문제 링크: https://www.acmicpc.net/problem/17298

문제

입출력

문제 접근

stack 문제이다.
현재 숫자보다 오른쪽에 있는 숫자중 크고 가장 왼쪽에 있는 숫자를 찾는 문제이다. stack으로 조건문 몇개만 넣어주면 되는 문제이다.
일단 자신보다 오른쪽에 있는 숫자들을 비교해야되기 때문에, 배열 끝에서 앞으로 가는 방향으로 구현하였다. 현재 배열의 값과 stack에 가장 top에 있는 숫자를 비교한다. 해당 숫자는 뒤에서 부터 넣기 때문에, 자신의 기준에서 가장 왼쪽에 있는 숫자부터 top에서 bottom으로 저장된다. top에 있는 숫자가 자신보다 크다면,해당 숫자를 값을 저장하고, 자신을 stack에 넣어준다.
만약 작다면, 해당 숫자를 stack에서 pop해준다. 어차피 자신보다 작고 오른쪽에 있기 때문에, 앞에 숫자들에 대해 풀 때, 고려대상이 되지 않는다.

라인 인턴 코테에서 stack문제를 못풀고, 반성하기위해 비슷한 문제들을 풀고 있다.

코드 구현(c++)

#include <iostream>
#include <vector>

using namespace std;

int nums[1000001];
int input[1000001];
vector<int> v;
int N;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    int temp;
    for(int i = 0 ; i < N ; i++){
        cin >> temp;
        input[i] = temp;
    }
    for(int i = N - 1 ; i >= 0 ; i--){
        if(i == N-1){
            nums[i] = -1;
            v.push_back(input[i]);
        }
        while(v.size()){
            if(v.back() > input[i]){
                nums[i] = v.back();
                break;
            }
            else v.pop_back();
        }
        if(v.size() == 0){
            nums[i] = -1;
        }
        v.push_back(input[i]);
    }
    for(int i = 0 ; i < N ; i++){
        cout << nums[i] << " ";
    }
    cout << "\n";
}

좋은 웹페이지 즐겨찾기