[백준-1874] 스택 수열

<문제>

---

<Code>

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

int main(){
  int n; //n개의 수를 입력 받음
  int number; //입력받을 정수
  int s=1; //임시 수열

  stack<int> st;
  queue<int> que;
  vector<char> result; //'-'와 '+'를 출력하기 위한 벡터 

  cin>>n; //8

  for(int i=0; i<n; i++){
    cin>>number;
    que.push(number);
  }

  while(que.size()){
    if(s<=que.front()){
      while(s<=que.front()){
        st.push(s++);
        result.push_back('+');
      }
    }else if(que.front()==st.top()){
      if(st.size()){
        st.pop();
        que.pop();
        result.push_back('-');
      }
    }else{
      cout<<"NO"<<"\n";
      return 0;
    }
  }

  for(auto c: result){
    cout<<c<<'\n';
  }
  return 0;
}

이게 초기 코드인데 여기서 한참을 헤맸다. 예제1을 입력하면 마지막에 '-' 세번이 덜 출력, 예제2를 입력하면 NO가 아니라 '+-+-+++' 가 출력된다.

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

int main(){
  int n; //n개의 수를 입력 받음.
  int number; //입력받을 정수.
  int s=1; //임시 수열

  stack<int> st;
  queue<int> que;
  vector<char> result; //'-'와 '+'를 출력하기 위한 벡터 

  cin>>n; //8

  //stack, queue에 다 넣음.
  for(int i=0; i<n; i++){
    cin>>number;
    st.push(number);
    que.push(number);
    //cout<<number<<endl;
  }

    for(int i=0; i<n; i++){
      if(que.size()){
        if(s<=que.front()){
          while(s<=que.front()){
          st.push(s++);
          result.push_back('+');
          }
        }else if(que.front()==st.top()){
          st.pop();
          que.pop();
          result.push_back('-');
        }else{
          cout<<"NO"<<"\n";
        }
      }
    }

  for(auto c: result){
    cout<<c<<'\n';
  }
  return 0;
}

---

<Comment>

1. queue에 다 넣음.

2. 입력받은 수<=queue의 front까지 수열 증가시키고 stack에 push

3. 증가시키다가 queue의 front와 stack의 top이 같으면 pop

4. 그 외에는 수열을 만들 수 없는 경우이므로 NO 출력

5. 문자열 출력<algorithm>

#include <stack>

#include <queue>

#include <vector>

using namespace std;

 

int main(){

  int n; //n개의 수를 입력 받음

  int number; //입력받을 정수

  int s=1; //임시 수열

 

  stack<int> st;

  queue<int> que;

  vector<char> result; //'-'와 '+'를 출력하기 위한 벡터 

 

  cin>>n; //8

 

  for(int i=0; i<n; i++){

    cin>>number;

    que.push(number);

  }

 

  while(que.size()){

    if(s<=que.front()){

      while(s<=que.front()){

        st.push(s++);

        result.push_back('+');

      }

    }else if(que.front()==st.top()){

      if(st.size()){

        st.pop();

        que.pop();

        result.push_back('-');

      }

    }else{

      cout<<"NO"<<"\n";

      return 0;

    }

  }

 

  for(auto c: result){

    cout<<c<<'\n';

  }

  return 0;

}

이게 초기 코드인데 여기서 한참을 헤맸다. 예제1을 입력하면 마지막에 '-' 세번이 덜 출력, 예제2를 입력하면 NO가 아니라 '+-+-+++' 가 출력된다.

 

#include <iostream>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

using namespace std;

 

int main(){

  int n; //n개의 수를 입력 받음.

  int number; //입력받을 정수.

  int s=1; //임시 수열

 

  stack<int> st;

  queue<int> que;

  vector<char> result; //'-'와 '+'를 출력하기 위한 벡터 

 

  cin>>n; //8

 

  //stack, queue에 다 넣음.

  for(int i=0; i<n; i++){

    cin>>number;

    st.push(number);

    que.push(number);

    //cout<<number<<endl;

  }

 

    for(int i=0; i<n; i++){

      if(que.size()){

        if(s<=que.front()){

          while(s<=que.front()){

          st.push(s++);

          result.push_back('+');

          }

        }else if(que.front()==st.top()){

          st.pop();

          que.pop();

          result.push_back('-');

        }else{

          cout<<"NO"<<"\n";

        }

      }

    }

 

  for(auto c: result){

    cout<<c<<'\n';

  }

  return 0;

}



<Comment>

 

1. queue에 다 넣음.

 

2. 입력받은 수<=queue의 front까지 수열 증가시키고 stack에 push

 

3. 증가시키다가 queue의 front와 stack의 top이 같으면 pop

 

4. 그 외에는 수열을 만들 수 없는 경우이므로 NO 출력

 

5. 문자열 출력

 

생각보다 시간이 너무 오래 걸렸다. 열심히 해야겠다.

---

www.acmicpc.net/problem/1874

1874번: 스택 수열