[c++] 백준 17298 오큰수

백준 단계별로 풀어보기 [스택] 오큰수

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

17298번: 오큰수

 

[풀이]

스택의 top에 저장된 인덱스의 배열 값과 비교하여 현재 배열 값이 더 크면 오큰수를 발견한 것이다. 따라서 오큰수를 발견한 값의 인덱스는 스택에서 pop해 지워준다. 오큰수에 해당하는 값은 ans[] 배열에 저장해준다.

스택의 top보다 현재 배열값이 더 작아지면 현재 배열값을 stack에 push해준다.  

for문이 종료되면 stack이 빌 때까지 stack에 남은 index에 대해 오큰수가 존재하지 않는 것이므로 ans[] 배열에 -1을 저장한다. 

예) [3, 5, 2, 7] 

index: 0 -> push(0) stack: (top) 0(3)

index: 1 -> arr[1] = 5 > arr[0] = 3이기 때문에 ans[] 저장 후 pop(). while 문 나와서 push(1).

stack: (top) 1(5) ans: [5, , , ]

index: 2 -> arr[2] = 2 < arr[1] = 5이기 때문에 push(2). stack: (top) 2(2) 1(5) ans: [5, , , ]

index: 3 -> arr[3] = 7 > arr[2] = 2이기 때문에 ans: [5,  , 7,  ] 저장 후 pop().

                             > arr[1] = 5이기 때문에 ans: [5, 7, 7, ] 저장 후 pop(). while문 나와서 push(3).

for문 나와서 ans[3] = -1 저장. ans: [5, 7, 7, -1].

 

[코드]

#include <iostream>
#include <algorithm>
#include <stack>

int main() {
	// 스택 오큰수
	int n; //수열의 크기
	std::cin >> n;
	std::stack<int> s;

	int* arr = new int[n];
	int* ans = new int[n];

	for (int i = 0; i < n; i++) {
		std::cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		if (s.empty())
			s.push(i);
		while (!s.empty() && arr[i] > arr[s.top()]) { //오큰수 발견
			ans[s.top()] = arr[i];
			s.pop();
		}
		s.push(i);
	}

	while (!s.empty()) {
		ans[s.top()] = -1;
		s.pop();
	}

	for (int i = 0; i < n; i++)
		std::cout << ans[i] << " ";
	
    delete[] arr, ans;
}