# 백준 : 스택 수열(1874)
문제
https://www.acmicpc.net/problem/1874소스
(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1874_stackseries)#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;
int main(void) {
int count, input, totalnum;
int number = 1; // 1부터 n까지 증가하는 숫자
vector<int> arr;
vector<string> result;
arr.push_back(number++);
result.push_back("+");
cin>>count;
totalnum = count;
for(int i=0; i<count; i++) {
cin>>input;
while(true) {
if(arr.back() == input) {
arr.pop_back();
result.push_back("-");
break;
}
else {
if(number > totalnum) {
cout<<"NO\n";
return 0;
}
else {
arr.push_back(number++);
result.push_back("+");
}
}
}
}
for(int i=0; i<result.size(); i++) cout<<result[i]<<"\n";
return 0;
}
풀이
이번 문제는 스택의 pop, push를 이용하여 입력된 순서대로 숫자를 출력할 수 있도록 하는 프로그램을 구현하는 것이다. 자그마치 정답률이 25% 전후인 문제인데 자랑스럽게도 '한.번.에' 맞췄다.물론 제출하기 전에는 생각할 부분들이 좀 있었지만, 그럼에도 제출시에 한번도 틀리지 않았다는 것은 엄청난 발전이고 뿌듯한 일이다. 컄.
각설하고, 내가 풀어낸 방식은 다음과 같다.
1. 내가 pop하고자 하는 숫자를 입력받는다.
2. 입력한 숫자가 나올 때까지 계속 1씩 증가하면서 숫자를 스택에 쌓는다.
3. 숫자가 나오면 pop하고 다음 숫자를 입력받는다.
이를 계속 반복하고 push일 경우에는 +를, pop인 경우에는 -를 출력해준다.
문제는 이런 방식으로 수열이 만들어지지 않는 경우에 NO를 출력해줘야 하는데, 이부분은 스택에 쌓이는 숫자가 실제 내가 입력하기로 한 숫자의 갯수보다 커지게 되는 경우에 출력하도록 하였다.
다시말하면, 어찌되었든간에 내가 8개의 정수를 입력하기로 했다면 그 결과는 최대 숫자 8이 스택에 쌓일때까지 수열이 만들어져야하는데, 9가 되면 결국 내가 입력하기로 한 숫자 갯수보다 더 커지게 되므로 이는 불가능하다고 판단하였다.
점점 발전해가는 실력에 뿌듯하구나.
댓글
댓글 쓰기