본문 바로가기
백준

[백준/C++] 1874 스택수열

by MY블로그 2023. 6. 13.
 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

이번 문제는 stack & vector 를 사용한 문제 입니다.

기본조건으로 오름차순의 수열을 만들기위하여 입력받은 n만큼의 입력을 반복 합니다.

스택의 top이 입력받은 m과 같다면 pop 시켜 ' - ' 를 벡터에 추가해주도록 합니다.

반대로 입력받은 m보다 작다면 스택에 push 시켜 ' + ' 를 벡터에 추가해주도록 합니다.

위의 두 경우를 만족시킬수 없을경우는 오름차순을 지킬 수 없으며,

수열을 만들수 없기 때문에 NO 를 출력후 종료합니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <map>
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

// 백준 1874 스택수열

int main() {
	fastio;
	stack<int> st; // 스택 사용
	vector<char> result; // 결과 저장할 벡터 배열
	int count = 1,n; // 카운트변수 & 반복횟수 입력받을 변수
	cin >> n; // 반복 횟수 입력
	for (int i = 0; i < n; i++){ // 반복횟수만큼 숫자 입력 받기
		int m; // 임시변수
		cin >> m; // 입력받기
		while (count <= m){ // 카운트의  숫자가 반복숫자보다 작거나같은경우
			st.push(count); // 스택에 카운트 붙여넣기 카운트는 1부터 반복횟수까지 쭉붙여넣기
			count++; // 분여넣고 카운트 증가
			result.push_back('+'); // 증가될때는 결과 벡터에 + 푸시백
		}
		if (st.top() == m){ // 스택의 top 부분과 입력받은수가 같다면
			st.pop(); // 스택의 top 부분을 pop 시킨다
			result.push_back('-'); // 스택에서 빠진결과는 - 로 붙이기
		}
		else { 
			// top이 입력받은 수보다 크다는 것은 오름차순의 수열을
			// 만들 수 없기때문에 종료시킨다.
			cout << "NO";
			return 0;
		}
	}
	for (int i = 0; i < result.size(); i++) // 결과 배열 출력
		cout << result[i] << '\n'; // 1줄에 1개출력이므로 줄바꿈필요
}

'백준' 카테고리의 다른 글

[백준/C++] 11286 절댓값 힙  (0) 2023.08.07
[백준/C++] 1976 여행 가자  (0) 2023.05.30
[백준/C++] 1717 집합의 표현  (0) 2023.05.24
[백준/C++] 14888 연산자 끼워넣기  (1) 2023.05.21
[백준/C++] 1912 연속합  (0) 2023.05.18

댓글