https://www.acmicpc.net/problem/1874
๋ฌธ์
์คํ (stack)์ ๊ธฐ๋ณธ์ ์ธ ์๋ฃ๊ตฌ์กฐ ์ค ํ๋๋ก, ์ปดํจํฐ ํ๋ก๊ทธ๋จ์ ์์ฑํ ๋ ์์ฃผ ์ด์ฉ๋๋ ๊ฐ๋ ์ด๋ค. ์คํ์ ์๋ฃ๋ฅผ ๋ฃ๋ (push) ์ ๊ตฌ์ ์๋ฃ๋ฅผ ๋ฝ๋ (pop) ์ ๊ตฌ๊ฐ ๊ฐ์ ์ ์ผ ๋์ค์ ๋ค์ด๊ฐ ์๋ฃ๊ฐ ์ ์ผ ๋จผ์ ๋์ค๋ (LIFO, Last in First out) ํน์ฑ์ ๊ฐ์ง๊ณ ์๋ค.
1๋ถํฐ n๊น์ง์ ์๋ฅผ ์คํ์ ๋ฃ์๋ค๊ฐ ๋ฝ์ ๋์ด๋์์ผ๋ก์จ, ํ๋์ ์์ด์ ๋ง๋ค ์ ์๋ค. ์ด๋, ์คํ์ pushํ๋ ์์๋ ๋ฐ๋์ ์ค๋ฆ์ฐจ์์ ์งํค๋๋ก ํ๋ค๊ณ ํ์. ์์์ ์์ด์ด ์ฃผ์ด์ก์ ๋ ์คํ์ ์ด์ฉํด ๊ทธ ์์ด์ ๋ง๋ค ์ ์๋์ง ์๋์ง, ์๋ค๋ฉด ์ด๋ค ์์๋ก push์ pop ์ฐ์ฐ์ ์ํํด์ผ ํ๋์ง๋ฅผ ์์๋ผ ์ ์๋ค. ์ด๋ฅผ ๊ณ์ฐํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ.
์ ๋ ฅ
์ฒซ ์ค์ n (1 ≤ n ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ n๊ฐ์ ์ค์๋ ์์ด์ ์ด๋ฃจ๋ 1์ด์ n์ดํ์ ์ ์๊ฐ ํ๋์ฉ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋ฌผ๋ก ๊ฐ์ ์ ์๊ฐ ๋ ๋ฒ ๋์ค๋ ์ผ์ ์๋ค.
์ถ๋ ฅ
์ ๋ ฅ๋ ์์ด์ ๋ง๋ค๊ธฐ ์ํด ํ์ํ ์ฐ์ฐ์ ํ ์ค์ ํ ๊ฐ์ฉ ์ถ๋ ฅํ๋ค. push์ฐ์ฐ์ +๋ก, pop ์ฐ์ฐ์ -๋ก ํํํ๋๋ก ํ๋ค. ๋ถ๊ฐ๋ฅํ ๊ฒฝ์ฐ NO๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด
// Authored by : seondal
// Co-authored by : -
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
stack<int> s;
vector<char> v;
s.push(0);
int n;
cin >> n;
int i=1;
while (n--){
int input;
cin >> input;
while(s.top() < input){
s.push(i);
v.push_back('+');
i++;
}
if(s.top() > input){
cout << "NO";
return 0;
}
while(s.top() == input){
s.pop();
v.push_back('-');
}
}
for(int i=0; i<v.size(); i++){
cout << v[i] << "\n";
}
return 0;
}
/*
*/
'๐ Baaaaaarking > 0x05๊ฐ - ์คํ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ G1][C++] ๋ฐฑ์ค 3015๋ฒ: ์ค์์์ค ์ฌ๊ฒฐํฉ (0) | 2022.02.16 |
---|---|
[BOJ G4][C++] ๋ฐฑ์ค 17298๋ฒ: ์คํฐ์ (1) | 2022.02.13 |
[BOJ G5][C++] ๋ฐฑ์ค 6198๋ฒ: ์ฅ์ ์ ์ ๊พธ๋ฏธ๊ธฐ (0) | 2022.02.13 |
[BOJ G5][C++] ๋ฐฑ์ค 2493๋ฒ: ํ (0) | 2022.02.12 |
[BOJ][C++] ๋ฐฑ์ค 10773๋ฒ : ์ ๋ก (0) | 2022.01.06 |