문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
풀이
말이 어려워서 그렇지 이해하면 생각보다 간단하다.
1 부터 n 까지의 숫자가 있을 때, 그 숫자를 stack에 넣었다 빼며 주어진 문제를 만들 수 있냐없냐를 구하면 된다.
주어진 예시1)을 살펴보자.
처음에 4가 왔으므로 stack에
1 2 3 4 이렇게 4 개를 push 해준다.
4를 출력해주기 위해 stack에서 4를 pop해준다.
다음으로 3이 와야 하므로 3또한 pop 해준다.
그 다음 숫자는 6이다. 6을 pop하기 위해서는 stack의 top에 6이 와야한다.
알맞게 push 해주면 stack에는
1 2 5 6 이 오게 된다.
6을 pop해서 출력해주고, 나머지 8 7 5 2 1 또한 위의 과정으로 pop 해주면 된다.
코드 구현은 다음과 같이 했다.
먼저 check 변수를 이용하여 n개의 숫자 중 어디까지 push 했는지 저장한다.
이후 출력해야 할 숫자(x로 정의)가 check 보다 작다면 stack에 x까지 push하고 '+'를 저장한다.
그리고 만약 stack의 top이 x와 일치한다면 pop을 의미하는 '-'을 저장하고 그렇지 않다면 잘못된 입력값(배열)이므로 NO를 출력해주었다.
코드
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
void init() {
ios_base::sync_with_stdio(false);
cin.tie(0);
}
int main() {
init();
stack<int> s;
vector<string> ans;
int check = 1;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
while (check <= x) {
s.push(check++);
ans.push_back("+");
}
if (s.top() == x) {
s.pop();
ans.push_back("-");
}
else {
cout << "NO";
return 0;
}
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << '\n';
}
return 0;
}
