백준 2493 c++ "탑" -PlusUltraCode-

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

 

 

[필자 사고]

대표적인 스택 자료구조를 묻는 알고리즘이다.

 필자는 알고리즘 전공 수업 때 스택관련 자료구조를 설명해주실 때 위와 비슷한 문제를 들어 설명해 주신 기억이 났다.

이 문제에서 키포인트는 다음과 같다.

현재 최상단의 스택의 값과 현재 입력으로 주어진 값을 비교하여 작은지 큰지에 따라 스택을 뺄지 널지 정하면 된다.

아래는 소스코드 해설이다.

 

[코드 해설]

 

• 스택 myStack을 사용하여 각 숫자에 대해 이전 숫자들을 처리한다.
  • 입력으로 주어진 수열을 하나씩 처리하면서, 현재 숫자보다 큰 이전 숫자를 찾기 위해 스택을 사용한다.
• 현재 숫자보다 큰 이전 숫자를 찾는 과정
  • 스택의 상단에 있는 숫자가 현재 숫자보다 크다면, 해당 숫자의 인덱스를 출력하고 현재 숫자와 인덱스를 스택에 추가한다.
  • 만약 스택 상단의 숫자가 현재 숫자보다 작다면, 더 큰 숫자를 찾기 위해 스택에서 제거한다.
• 스택이 비어 있는 경우
  • 스택이 비어 있다면, 현재 숫자보다 큰 이전 숫자가 없음을 의미하므로 0을 출력하고, 현재 숫자와 인덱스를 스택에 추가한다.
• 입력 수열의 모든 숫자를 순서대로 처리
  • 입력으로 주어진 N개의 숫자를 차례로 읽어들이며 위의 과정을 반복한다

 

[소스 코드]

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

using namespace std;

int N;
stack<pair<int,int>> myStack;

void Input() {
	cin >> N;


}

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

		while (!myStack.empty()) {
			if (myStack.top().second > num) {
				cout << myStack.top().first << " ";
				myStack.push({ i + 1,num });
				break;
			}
			else {
				myStack.pop();
			}
		}

		if (myStack.empty()) {
			cout << 0 << " ";
			myStack.push({ i + 1,num });
		}
	}
}

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

	Input();
	Game_Start();
}