BOJ 1874] 스택 수열

[ 문제 이해 ]

입력 값

예) 3 5 1 2 4

- 1부터 n까지의 수를 순서대로 스택에 넣는다. (+출력)

스택 : 1 2 3

 

- 위를 하다 입력된 값과 같아지면 그 수를 스택에서 제거한다 (-출력)

스택  : 1 2 (3제거)

스택 : 1 2 4 (5제거)

이런 식으로...

 

- 위 과정을 몇번해서 스택이 비워지고, 해당 수열이 완성되는 지 총 횟수를 출력한다

- 만약 위 과정을 진행하다 수열이 만들어지지 않으면 NO를 출력한다.

 

[ 접근법 ]

1. 스택에 1부터 1씩 증가하면서 스택에 넣는다.

2. 입력받은 값이 스택의 top 과 같아지면 스택을 pop()한다.

3. 1,2 과정을 반복하다 스택이 비워지면 종료

4. 만약 위 과정 중 스택이 입력값이 스택의 topp()보다 크면 "NO" 를 출력하고 프로그램을 종료한다.

 

[ 시행 착오 ]

1. +와 -를 즉시 출력하게 하면, NO가 출력되는 예시도 +,-가 같이 출력되어 오답처리된다.

2. 처음에는 입력된 값을 Queue에 집어넣어 하나씩 빼는 식으로 했는데, 시간 초과가 떳음.

 

[ 코드 보기 ]

#include <iostream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;


stack<int> s;
vector<char> res;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n, temp, idx = 1;
bool chk = false;


cin >> n;


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

if (s.empty() || temp > s.top()) {

if (idx > n) {
cout << "NO" << "\n";
return 0;
}
for (; idx <= temp; idx++) {
s.push(idx);
res.push_back('+');
}

}

if (temp == s.top()) {
s.pop();
res.push_back('-');
continue;
}

if (!s.empty() && temp < s.top()) {
cout << "NO" << "\n";
return 0;
}

}





for (int i = 0; i < res.size(); i++) {
cout << res[i] << "\n";
}


 
 return 0;
}