문제
문제 설명
일련의 수열을 만들기 위한 스택 연산을 +, -로 출력한다. +는 push, -는 pop을 뜻한다.
코드
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
int idx = 0;
int MAX = 1;
bool fail = false;
vector <string> calc;
vector <int> save;
stack <int> stk;
for (int i = 0; i < n; i++) {
int num; cin >> num;
save.push_back(num);
}
stk.push(1);
calc.push_back("+");
while (idx < n) {
if (fail) {
cout << "NO\n";
return 0;
}
if (stk.empty()) {
stk.push(MAX + 1);
calc.push_back("+");
if (MAX < stk.top()) MAX = stk.top();
continue;
}
if (save[idx] > stk.top()) {
for (int i = MAX + 1; i <= save[idx]; i++) {
stk.push(i);
calc.push_back("+");
}
}
else if (save[idx] < stk.top()) fail = true;
else {
if (MAX < stk.top()) MAX = stk.top();
stk.pop();
idx++;
calc.push_back("-");
}
}
for (auto it : calc) cout << it << '\n';
}
코드 설명
핵심은 수열의 값과 스택의 최상위 값 비교, 수열의 인덱스 관리이다.
- 수열의 값 > 스택의 최상위 값 : 지금까지 스택에 넣은 값 중 최대값 + 1부터 수열의 값까지 push. 단, 수열의 인덱스는 그대로 둔다.
- 수열의 값 = 스택의 최상위 값 : 최대값 갱신 후 스택의 최상위 값을 pop. 단, 수열의 인덱스를 +1 증가시켜 준다.
- 수열의 값 < 스택의 최상위 값 : 스택 수열을 만들 수 없는 구조이므로 0을 출력 후 프로그램 종료.
여담
스택 또는 큐를 사용할 때, empty( ) 함수나 top( ) 함수를 조심해서 사용해야 하는 불편함이 있다.
이를 해소하고자, 맨 처음에 무의미한 값 등[ex. -1, '0']을 push 해두면 empty와 top을 나름 자유롭게 구사할 수 있다.
다만 만능은 아니므로 필요한 때에 적절히 사용하도록 하자.
'Koala - 11기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[백준/python3] 12789번: 도키도키 간식 드리미 (0) | 2023.08.20 |
---|---|
[백준/python3] 18406번 (0) | 2023.08.14 |
[백준/Python] 7795번: 먹을 것인가 먹힐 것인가 (0) | 2023.08.13 |
[백준/Python3] 3062번: 수 뒤집기 (0) | 2023.08.13 |
[백준/C++] 5533번: 유니크 (0) | 2023.08.11 |