minjgziii

📍 문제

📍 풀이

• 자료구조 스택 활용
• 입력 받은 원소들을 스택에 담아, top(가장 마지막으로 입력 받은 원소)부터 오큰수를 구한다 => 역순으로!
• 구한 오큰수들도 스택에 담기 때문에 답을 출력할 때, [ top 원소 출력, pop ] 를 반복하면 순서대로 출력됨

☑️ 맨 마지막에 입력 받은 원소 (스택에서 top에 있는 원소)는 항상 오큰수가 없다.

따라서, 반복문을 돌기 전에

s1(오큰수 후보들)에 마지막 원소를 push하고,

s(오큰수를 구할 원소들)에서 pop하고,

answer(답을 담을 stack)에 -1을 삽입한다.

☑️ 반복문을 돌며 다음 조건문들에 따라 경우가 나뉜다.

1. s1(오큰수 후보들) 사이즈가 0인 경우 즉, s1에 원소가 하나도 없는 경우 => 오큰수가 없는 경우
2. s(현재 오큰수를 구하고 있는 원소)의 top보다 s1(오큰수 후보들) 의 top이 큰 경우 => 오큰수 후보가 됨
3. 현재 비교한 값은 오큰수가 아니지만, s1(오큰수 후보들) 사이즈가 0이 아닌 경우 => 아직 오큰수가 될 수 있는 후보가 있음 (아직 비교할 원소가 남아 있다!)

✥ 각 조건문마다 실행되는 과정은 코드 주석 참고

다음 그림에서 [ 파랑 -> 빨강 -> 초록 -> 보라 -> 노랑 ] 순으로 실행된다.

📍 코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int A = 0; // 수열 A의 크기
	int number;
	stack<int> s; // 오큰수를 구할 원소들
	stack<int> s1; // 현재 원소의 오큰수 후보들
	stack<int> answer; // 구한 원소들 (답)
	

	cin >> A;
	
	for (int i{ 0 }; i < A; i++) {
		cin >> number;
		s.push(number);
	}

	s1.push(s.top()); // s1에 s의 top(마지막 원소) 삽입
	s.pop(); // s에서 top 원소 삭제
	answer.push(-1); // 맨 마지막 원소는 항상 오큰수 없음 (즉, -1)

	while (s.size() > 0) {
		// s1에 원소가 하나도 없는 경우 -> 오큰수가 없음
		if (s1.size() == 0) {
			answer.push(-1); // 오큰수 없기 때문에 답을 넣을 스택에 -1 push
			s1.push(s.top()); // 다음 원소 비교를 위해 s1에 s의 top 원소 삽입
			s.pop();
		}
		// s의 top보다 s1의 top이 큰 경우 -> 오큰수 후보/
		else if (s.top() < s1.top()) {
			answer.push(s1.top());
			s1.push(s.top());
			s.pop();
		}
		// 오큰수가 없지만, s1의 size가 0이 아닌 경우 (아직 오큰수가 될 수 있는 후보가 있음)
		else {
			s1.pop();
		}
	}

	for (int i{ 0 }; i < A; i++) {
		cout << answer.top() << " ";
		answer.pop();
	}
}