백준 1874 스택 수열 c++ [컴공과고씨]

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

1874번: 스택 수열

stack은 LIFO를 가지고 있기 때문에 이 규칙을 지켜서 문제 맞게 수행 해주면 된다.

내가 풀이 방법은 일단 스택이 있고 이 스택에는 미리 저장해놓은 원하는 수열 원소 크기와 비교해가면서 숫자를 순서대로 넣기 시작한다. 일단 원하는 원소 크기가 스택 top에 있는 숫자보다 크다면 원소 크기가 될때까지 숫자를 넣어주어야한다. 그런데 여기서 원하는 원소 크기가 다음 넣을 숫자 보다 작다면 수열을 만들 수 없기 때문에 no를 출력해준다.

원하는 원소 크기가 스택 top보다 작을 경우 스택에서 pop을 해주어야 한다.

원하는 원소크기와 스택 top과 같은 경우 pop을 해준 후 다음 원하는 원소크기를 비교하는 것으로 넘어가주면 된다.

이때 카운트를 기록해서 모든 원소를 확인했을 경우 반복문을 종료한다.

 

자세한 설명은 코드 주석에 달아놓았다.

 

전체 코드

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
int main(){
    int num[100002];
    int n;
    string result = ""; // 답을 저장할 변수
    cin >> n;
    for (int i = 0; i < n;i++){
        cin >> num[i]; //주어진 수열 저장
    }
 
    int cnt = 0;
    int next = 1;
    stack<int> st;
    bool flag = true;
    while(flag){
        if (st.empty()){ // 스택이 비었다면
            if(num[cnt]<next){ //원하는 원소 크기가 다음 넣어줄 숫자보다 작다면 수열을 만들 수 없음
                cout << "NO";
                return 0;
            }
            st.push(next); // 다음 숫자를 넣어준다.
            result += "+";
            next++;
        }
        else if(num[cnt] > st.top()){ //원하는 원소 크기가 스택 top에 있는 원소보다 크다면 숫자를 넣어주어야함.
            if(num[cnt]<next){ //원소 크기만큼 숫자를 넣어주어야하는데 다음 숫자가 원소크기보다 더 크다면 수열을 만들 수 없음.
                cout << "NO";
                return 0;
            }
            st.push(next); 
            next++; 
            result += "+";
        }
        else if(num[cnt] < st.top()){ // 원하는 원소 크기가 스택 top보다 작다면 스택에 숫자를 빼면서 찾아주어야함.
            st.pop();
            result += "-";
        }
        else if (num[cnt] == st.top()){ // 원하는 원소 크기와 스택 top과 같다면 다음 원하는 원소로 이동 cnt++
            result += "-";
            st.pop();
            cnt++;
            if(cnt == n){ // 모든 원하는 원소를 확인했다면 while문 종료
                flag = false;
            }
        }
    }
    for (int i = 0; i < result.length();i++)
    {
        cout << result[i] << '\n';
    }
 
    return 0;
}

사용 문법 stack

 

yea!