하다보니

1874번-스택 수열 본문

알고리즘 풀이/백준

1874번-스택 수열

claire 2022. 1. 22. 22:10
#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	stack<int> s;
	int cnt = 1;
	string ans;
	while (n--) {
		int t;
		cin >> t;
		while (cnt <= t) {
			s.push(cnt++);
			ans += "+\n";
		}
		if (s.top() != t) {
			cout << "NO\n";
			return 0;
		}
		s.pop();
		ans += "-\n";
	}
	cout << ans;
}

이 문제는 처음 봤을 때 이해가 안됐다. 그러니까 최종으로 만들어야하는 수열의 형태가 입력으로 주어지고 스택에 push할 때는 오름차순의 형태(1,2,3,4...)이렇게 순서를 꼭 지킨다는 말이다. 그러다보니 순열에 들어갈 해당 숫자 이전의 수들을 모두 스택에 넣고 pop을 했을 때 제일 위의 숫자가 순열에 들어갈 숫자가 아니라면 NO!를 출력한다. 

'알고리즘 풀이 > 백준' 카테고리의 다른 글

10845번-큐  (0) 2022.01.23
2493번-탑  (0) 2022.01.22
10773번-제로  (0) 2022.01.22
5397번-키로거  (0) 2022.01.18
1406번-에디터  (0) 2022.01.17