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

서론

단순하게 이중반복문을 사용하면 시간초과

아이디어

현재 수와 다음 수들을 크기비교해야 하는데 스택을 이용할 수 있다.

현재 수가 스택의 탑보다 큰경우 탑을 출력함과 동시에 팝하는것을 반복한 후 현재 수를 스택에 넣으면 된다.

현재 수가 스택의 탑보다 크다는것은 현재 수가 스택의 탑(현재 수보다 이전에 나온 수)의 오큰수가 된다.

입력이 3 5 2 7일 때

1. 처음 3은 그대로 푸시

2. 5는 스택의 탑인 3과 비교하여 3보다 크니 5(3의 오큰수)를 출력하고 3을 팝, 5를 푸시

3. 2는 5보다 작으므로 그대로 푸시

4. 7은 스택의 탑인 2보다 크니 7을 출력하고 2를 팝, 다시 스택의 탑인 5보다 크므로 7을 다시 출력하고 5를 팝, 7을 푸시

5. 입력이 끝났으므로 스택이 빌때까지 -1을 출력

구현은 출력부분의 수정이 필요한데,

예를들어 입력이 9 1 2 3과 같을떄 출력이 -1 2 3 -1이 되야하는데 위 아이디어는 시작할때나 중간에 -1을 출력할 수 없다.

따라서 계산 도중에 출력하는것이 아닌, 결과배열에 순서를 잘 맞춰서 저장한 후 마지막에 결과값을 한번에 출력해야한다.

구현

//c++

#include <iostream>
#include <stack>
#include <cstring>

int result[1000001];

int main() {
	int n;
	memset(result, -1, sizeof(result));
	std::stack<std::pair<int, int>> s;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		int cur;
		std::cin >> cur;
		if (s.size() == 0) s.push({ cur, i });
		else {
			while (cur > s.top().first) {
				result[s.top().second] = cur;
				s.pop();
				if (s.size() == 0) break;
			}
			s.push({ cur, i });
		}
	}
	for (int i = 0; i < n; i++) std::cout << result[i] << " ";
}