https://www.acmicpc.net/problem/1874
문제 해결 과정
착안
수열을 만들 수 있는지 확인하는 별다른 방법이 떠오르지는 않아, 문제에서 제시한 과정을 그대로 구현하여 문제를 해결하고자 하였다. 구체적으로는 아래와 같이 구현하고자 했다.
- 스택이 비어있거나 Top에 위치한 요소가 현재 수열의 항보다 작으면 push를 반복
- (위 반복이 끝난 후) 스택의 Top에 위치한 요소가 현재 수열의 항과 같으면 pop 수행, 같지 않으면 중단
구현
위의 과정은 수를 입력받을 때마다 실행할 수 있는 과정이므로 이 점에 중점을 두어 구현하였다. 정확하게 스택에서 push 또는 pop을 실행하는 횟수는 알 수 없기 때문에 std::vector<> 클래스를 활용하여 저장하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<char> Op;
stack<int> S;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, n = 1;
cin >> N;
for (int i = 0; i < N; i++)
{
int num;
cin >> num;
while (S.empty() || S.top() < num)
{
Op.push_back('+');
S.push(n++);
}
if (S.top() == num)
{
Op.push_back('-');
S.pop();
}
else
{
cout << "NO\n";
return 0;
}
}
for (char c : Op)
cout << c << "\n";
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 11866번: 요세푸스 문제 0 (0) | 2023.06.14 |
---|---|
[Baekjoon] 11047번: 동전 0 (0) | 2023.06.13 |
[Baekjoon] 1181번: 단어 정렬 (0) | 2023.06.11 |
[Baekjoon] 11650번: 좌표 정렬하기 (0) | 2023.06.11 |
[Baekjoon] 2579번: 계단 오르기 (0) | 2023.06.09 |
댓글