https://www.acmicpc.net/problem/1874
문제 분석
1부터 n까지의 수를 스택에 넣어놓고 입력받은 수열을 만들기 위해 push와 pop연산을 어떻게 수행해야 하는지 출력하는 문제다. push연산을 수행할 땐 +, pop연산을 수행할 땐 -를 출력한다. 입력받은 수열을 만들 수 없는 경우에는 NO를 출력한다.
코드
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(){
cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
vector<char> ans;
stack<int> save;
int cnt = 1;
int n; cin>>n;
int tmp;
for(int i=0; i<n; i++){
cin>>tmp;
while(cnt<=tmp){
save.push(cnt);
cnt++;
ans.push_back('+');
}
if(save.top() == tmp){
save.pop();
ans.push_back('-');
}
else{
cout<<"NO";
return 0;
}
}
for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";
return 0;
}
문제 풀이
- 출력값들을 저장할 벡터 ans와 스택 save를 선언한다. 변수 cnt를 1로 설정한다.
- 수들의 개수 n을 입력받고, 변수 tmp를 선언해 for문 안에서 tmp를 입력받는다.(수열)
- cnt가 tmp보다 커질 때까지 while문으로 save에 cnt값을 push하고 push연산을 수행했으므로 ans에 +를 push한다. cnt는 while문이 돌 때마다 증가하도록 하여 같은 값이 들어가지 않도록 한다.
- cnt가 tmp보다 크고 save의 top값이 tmp와 같다면 뽑아내서 수열로 만들어야 하므로 pop하고 pop연산을 수행했으므로 ans에 -를 push한다. 만약 save의 top값이 tmp와 다르다면 입력받은 수열을 만들 수 없다는 뜻이므로 NO를 출력하고 프로그램을 종료한다.
- 수열을 만들 수 있다면 ans에 저장된 +, -들을 출력한다.
'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/JAVA] 11003 최솟값찾기 (0) | 2022.08.06 |
---|---|
[백준/C++] 2164 카드 2 (0) | 2022.08.05 |
[백준/C++] 17612번 쇼핑몰 (0) | 2022.08.04 |
[백준/python] 6236번 용돈관리 (0) | 2022.07.31 |
[백준/Python] 6236번: 용돈 관리 (0) | 2022.07.31 |