[BOJ] 25556번_포스택_스택 (C++)

[문제]

https://www.acmicpc.net/problem/25556

길이가 N인 순열 A와 4개의 스택이 있다.

순열 A를 오름차순으로 정렬하려고 하는데, 이때 4개의 스택을 이용할 것이다. 스택을 사용하는 방법은 다음과 같다.

1. 순열 A의 원소들을 앞 원소부터 순서대로 4개의 스택 중 하나에 삽입한다.
2. 순열 A의 모든 원소를 스택에 삽입했다면, 4개 중 원하는 스택에서 수를 꺼내는 것을 반복하여 4개의 스택에서 모든 수를 꺼낸다.
3. 꺼낸 수들을 꺼낸 순서대로 오른쪽에서 왼쪽으로 나열한다. 즉, 가장 처음에 꺼낸 수가 맨 뒤, 가장 나중에 꺼낸 수가 맨 앞에 위치하게 된다.

위와 같은 방법으로 순열을 오름차순 정렬할 수 있는지 판별하는 문제이다. 정렬가능하면 "YES", 불가능하면 "NO"를 출력하자.

[사용 알고리즘]

스택

[풀이 핵심]

• 스택에서 뺀 수를 뒤에서부터 배치하여 오름차순으로 정렬되어야하므로 스택은 작은수부터 넣어서 top에 가장 큰수가 오도록 해야한다. 따라서 넣으려는 수가 스택의 top보다 작을 경우 오름차순으로 정렬이 불가능한 것이다.
• 스택이 비어있으면 순열의 값을 바로 넣고, 비어있지 않으면 넣으려는 값이 스택의 top보다 클경우 스택에 넣으면 된다. 넣으려는 값이 스택 4개의 top보다 작을 경우 pushCheck변수를 통해 오름차순으로 정렬이 불가능하다는 것만 체크해주면 쉽게 풀 수 있다.

[코드]

//boj25556번_포스택_스택

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<stack<int>> v(4);
	bool check = true;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;

		bool pushCheck = false;

		for (int j = 0; j < 4; j++) {
			if (v[j].empty()) {
				v[j].push(num);
				pushCheck = true;
				break;
			}
			else {
				if (v[j].top() < num) {
					v[j].push(num);
					pushCheck = true;
					break;
				}
			}
		}
		if (!pushCheck) {
			check = false;
			break;
		}
	}


	if (check) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}

	return 0;
}