본문 바로가기
알고리즘

[백준 1874] 알고리즘 39일차 : 스택 수열

by SiO2whocode 2020. 8. 7.
반응형

https://www.acmicpc.net/problem/1874

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

스택 C++

처음에 문제 이해를 못해서 이해하는데 시간이 좀 걸렸다.

1부터 n까지의 수가 연속된 수라는 점을 이해하면 된다.

1부터 n까지의 수가 섞여있는 수열이 주어지고 나는 1,2,3,4,...,n 까지의 수를 순서대로 스택에 push할 수 있고

또 pop하면서 결과적으로 pop하여 만들어진 수열이 입력된 수열이 되도록 하는 것

 

접근방법

입력받을 수 만큼의 반복문을 돌면서 (반복문 한번에 숫자 하나씩 입력받는다.)

스택의 top과 입력받은 수(num)를 비교한다.

스택이 비었거나(초기상태 대비) top < num 이면

top에 num에 해당하는 수가 올때까지 push한다.

top == num 이면

pop한다.

그리고 top > num 이면

NO를 출력하고 프로그램을 끝낸다.

 

flag용 변수를 남발해서 이렇게 지저분한 코드가 없다. 하면서 제출했는데

의외로 한번에 통과돼서 기분 좋았다. 오늘은 이따 낮에 바쁠 것 같아서 지금 올려둠!

 

소스코드

#include <iostream>
using namespace std;
class Stack{
public:
    int size;
    int* stack;
    Stack(int maxSize){
        size = 0;
        stack = new int[maxSize];
    }
    void push(int n){
        stack[size++] = n;
    }
    int pop(){
        if(isEmpty()){
            return -1;
        }
        else{
            return stack[--size];
        }
    }
    int getSize(){
        return size;
    }
    bool isEmpty(){
        if(size == 0)
            return true;
        else
            return false;
    }
    int top(){
        if(isEmpty()){
            return -1;
        }
        else{
            return stack[size-1];
        }
    }
};
int main(){
    int n;
    cin >> n;
    Stack s = Stack(n);
    
    char result[2*n];
    int cnt = 0;
    int num;
    for(int i = 1, a = 1 ; i <= n ; i++){
        cin >> num;
        while(s.isEmpty() || s.top() < num){
            s.push(a++);
            result[cnt++] = '+';
        }
        if(s.top() == num){
            s.pop();
            result[cnt++] = '-';
        }
        if(s.top() > num){
            cout << "NO";
            return 0;
        }
    }
    for(int i = 0 ; i < 2*n ; i++)
        cout << result[i] << "\n";
    return 0;
}
반응형

댓글0