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를 출력한다.접근
문제가 입력으로 주어진 N개의 수들이 수열이고 이를 1부터 n까지 스택에 넣었다 뻈다를 적절히 써서 그 수열을 만들으라는 문제다. 이해가 좀 어려웠다.
일단 큐가 비었거나 수열의 첫번째 수보다 넣으려는 수가 작다면 수열의 첫 수가 될 때까지 쭉 넣는다. 넣으면서 결과 벡터에 + 추가해준다.
다 넣고나면 수열의 첫 수와 스택에있는 top()의 수가 같으니까 이를 pop하고 -를 결과에 누적한다.
이제 수열의 다음 수를 보는데 만약 다음 수가 넣어야될 수보다 크면 다시 넣고 작으면 현재 스택에 있는 top()을 본다. 둘이 같다면 또 pop하고 아니면 NO출력하고 끝낸다.
이걸 반복한다.
문제해결
> 수열을 구성하는 수의 개수를 입력받고 수열을 입력받아 생성한다. 결과 +,-를 저장할 벡터와 스택을 선언하고 넣을수 i를 1부터로 선언해준다.
> 수열벡터 num을 순회하며 볼것이기 때문에 t에대해 반복문을 돌린다. t는 num의 인덱스이다.
> 일단 접근에서 말했듯이 스택에 num의 첫수(t가 0일때)와 같을때 까지 i를 넣는다. 넣었으니 결과에도 +를 누적해주고 i를 증가시켜준다.
> 이제 이 과정이 끝나면 현재 스택의 top이 num값과 같다는 뜻이므로 해당 값을 pop하고 결과를 누적한다.
이 과정을 반복해 결과를 낸다.
> else문은 위 과정에 위배되는 예외에 대한 처리이다. 넣어야할 i가 num보다 커서 if문으로 왔더니 top이 num과 다른값일 때 더 이상 push나 pop으로 처리할수 없을 때 이다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>
#include <sstream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> num(n);
for (int i = 0; i < n; i++)
cin >> num[i];
vector<char> rst;
stack<int> s;
int i = 1;
for(int t = 0; t < n; t++)
{
while(i <= num[t])
{
s.push(i);
rst.push_back('+');
i++;
}
if (s.top() == num[t])
{
rst.push_back('-');
s.pop();
}
else
{
cout << "NO" << '\n';
return 0;
}
}
for (auto& a : rst) cout << a << '\n';
}
후기
for문의 구조를 일단 글로 다 짜놓고 들어갔는데 막상 다 만들고 나니 예외도 생기고 불필요한 조건들, 겹치는조건도 생기고 구멍이 많았다. 구조를 견고하게 짜는 연습을 더 열심히 하자.
그리고 출력 초과 오류가 계속나 뭐가 문제일까 했는데 처음에 rst.push_back없이 cout으로 해줬더니 최악엔 200,000번 출력을 해야하므로 오류가 난다는것이었다.
