[백준] 1874번 : 스택 수열 / c++

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

1874번: 스택 수열

 

 

솔직히 기본적으로 문제 이해를 하는 데 있어서부터 꽤 애를 먹었다.

 

※ 수열이란?

일정한 규칙에 따라 한 줄로 배열된 수의 열. a₁, a₂, a₃,…, aₙ의 꼴로 배열한 것으로, ｛aₙ｝로 나타냄. 등차수열·등비수열·조화수열 등이 있음.

 

그래서

이런 식으로 생각해버렸는데 입력에 보면 n이 주어질 때 1이상 n이하의 정수가 하나씩 순서대로 주어진다는 걸 보면 n이 주어질 때 그 이하의 '모든 수'로 스택을 만든다는 것부터 이해를 제대로 하지 못하였다.

 

또 각 항목이 전체가 push 되어 있을 때부터 시작하는 것이라 생각해 또 헤맸다.

 

 

 

 

 

위는 내가 헤맨 이유이고

설명은 여기부터 보시면 된다.

 

[ 예제 설명 ]

예제 1에서

모든 항목을 8까지 쓸 때, 처음에 4가 나오려면 push를 4번하고 (+를 4번 cout) pop을 한번하면 (-를 한번 cout) 나온다.

다음 이미 4까지 push했었고, 이미 한번 pop한 상태이니 3을 원하면 그대로 pop을 한번 더 해주면 된다. (-를 한번 cout)

6을 원하면 5,6을 두번 push한뒤 pop해주면 된다. (+를 2번, -를 한번)

 

 

[ 코드 ]

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

int main() {
  int N;
  vector<int> vec;
  stack<int> arr;
  vector<string> s;
  int j =0;
    
  cin >> N;
  
  for (int i=0; i<N; i++) {
    int tmp;
    cin >> tmp;
    vec.push_back(tmp);
  }
  for (int i=1; i<=N; i++) {
    arr.push(i);
    s.push_back("+");
    
    while(!arr.empty() && arr.top() == vec[j]){
      int tmp = vec[j];
      arr.pop();
      s.push_back("-");
      j++;
    }
  }
  if (!arr.empty()) {
    cout << "NO" << endl;
  } else {
    for (int i=0; i< s.size(); i++) {
      cout << s[i] << "\n";
    }
  }

  return 0;
}

 

백준에서 특이한 것은 마지막 cout문에서 "\n"을 endl로 바꾸면 시간초과로 채점이 되지 않는다는 것이다..!

심지어 그 위의 NO 경우의 cout문에서는 endl이 먹히는 데 말이다.

다른 문제에서는 전혀 발생하지 않는 문제였는데, 그냥 외부에서 돌리면 되는 것이 백준에선 되지가 않는다.

 

 

 

계속 맨 위 경우처럼 뜨다가 시간 초과로 가버리니

혹 다른 분들도 그런 이슈가 있다면 참고하시길.