개인공부용123 프로그래밍 블로그

[백준] 1874(스택) 본문

알고리즘문제

[백준] 1874(스택)

개인공부용123 2017. 5. 2. 20:20

제목에서 아시다시피 스택수열입니다..  그렇습니다 스택을 사용해서 풀어보겠습니다.


이 문제는 인풋으로주어진 수열을 스택의 push, pop연산을 이용해서 표현할수있는가를 묻는 문제입니다.

이문제의 포인트는 현재 스택의 top값이 만들려는 수열의 값보다 크면 안된다는것입니다.

왜냐하면 스택의 입력은 1부터 차례대로 주어지게됩니다. 그리고 스택의 특성인 FILO(후입 선출)의 특성상 이후 스택에 들어올수있는 값은 적어도 스택의 top보다 크기때문입니다.


아래는 해당 소스 코드입니다.



#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	stack st;
	string str;
	int K;

	int N;
	cin >> N;
	
	int max = 0;

	for (int i = 0; i < N; ++i) {
		cin >> K; // 수열에 넣을 값
		if (K > max) {
			for (int j = max; j < K; ++j) {
				st.push(j + 1);
				str += "+\n";
			}
		}
		else if (st.top() > K) {
			cout << "NO" << endl;
			return 0;
		}

		st.pop();
		if (i == N - 1) str += "-";
		else str += "-\n";
		if (max < K) max = K;
	}
	
	cout << str << endl;

	return 0;
}


'알고리즘문제' 카테고리의 다른 글

[백준] 1260  (0) 2017.05.04
[백준] 9012  (0) 2017.05.02
[백준] 1929 (에라토스테네스의 체)  (0) 2017.05.02
[백준] 9426(세그먼트 트리)  (0) 2017.04.29
AlgoSpot) GRADUATION  (0) 2017.03.16