Memo
너무 어렵다...
input
N 개의 비교할 수열을 입력받는다.
vector resize를 활용해서 입력받았다.
solution
문제의 핵심은 스택에 들어올 숫자들이 1부터 N 까지 순서대로 들어온다는 것이다.
예를들어 아래와 같은 인풋이 들어온다면
3
2 1 3
YAML
복사
우리는 스택과 순서대로 들어올 1, 2, 3을 활용해서 [2, 1, 3] 을 만들어야한다.
output
1 부터 N 까지 들어오는 수열과 1 부터 N 까지를 활용하는 스택이기 때문에 마지막 남은 숫자가 다른 경우는 존재하지 않는다. 따라서 비어있지 않은 경우는 무조건 출력이 불가능하다는 것을 알 수 있다.
스택이 전부 비어있는 경우 스택을 활용해 표현 가능한 배열이기 때문에 out 문자열을 하나씩 출력해주면 된다.
Code
제출 날짜
@4/3/2021
메모리
3012 KB
시간
20 ms
#include <iostream>
#include <stack>
#include <vector>
std::vector<int> arr;
std::stack<int> stk;
std::string out;
int N;
void output()
{
if (!stk.empty())
std::cout << "NO";
else
{
for (size_t i = 0; i < out.size(); ++i)
std::cout << out[i] << '\n';
}
}
void solution()
{
int idx = 0;
for (int i = 1; i <= N; ++i)
{
stk.push(i);
out += "+";
while (!stk.empty())
{
if (stk.top() == arr[idx])
{
stk.pop();
out += "-";
++idx;
}
else
break;
}
}
}
void input()
{
std::cin >> N;
arr.resize(N);
for (int i = 0; i < N; ++i)
std::cin >> arr[i];
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
output();
}
C++
복사
