백준 1874 - 스택 수열(복습)

문제 링크입니다 https://www.acmicpc.net/problem/1874

1874번: 스택 수열

스택(stack)이란 기본적인 자료구조로 한쪽 끝에서만 자료를 넣고 뺄수 있는 LIFO(last in first out) 형식을 따릅니다.

 

스택 push, pop등 다양한 연산을 사용할 수 있습니다.

• push(num) -> num을 가장 위에 하나 추가한다.
• pop()        -> 가장 위에 있는 항목을 제거한다.
• peek()       -> 가장 위에 있는 항목을 반환한다.
• empty()     -> 스택이 비어있을때 false를 반환합니다.

1부터 n까지의 수를 스택에 입력했을때 연산을 이용해 원하는 수열을 만들 수 있는지 확인하는 문제입니다.

1부터 8까지의 수를 입력했을때 4 3 6 8 7 5 2 1의 수열을 만들고 싶다고 하면

+ + + + - - + + - + + - - - - -(+ -> push,  - -> pop) 와 같은 연산을 하면 만들 수 있습니다.

 

코드는 간단합니다. 

1. i를 push합니다(i는 1부터N까지 순서대로 증가)

2. 입력한 값이 원하는 수열의 첫번째 숫자와 같다면 pop해줌과 동시에 다음 숫자로 넘어갑니다

3. 1번과 2번을 반복합니다.

 

자세한 것은 코드를 참고해 주세요

 

#define CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int arr[100001];

int main() {
	cin.tie(0);
	cout.tie(0);
	stack<int> s;
	vector<char> v;
	int num, cnt = 1;
	cin >> num;
	for (int i = 1; i <= num; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= num; i++) {
		s.push(i);
		v.push_back('+');
		while (!s.empty() &&  s.top() == arr[cnt]) {
			s.pop();
			v.push_back('-');
			cnt++;
		}
	}
	if (!s.empty()) cout << "NO";
	else {
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << "\n";
		}
	}
	return 0;
}

 

질문 및 조언 댓글 남겨주세요