백준 17298. 오큰수

오큰수

오른쪽에서 가장 큰 수 라는 뜻

별걸 다 줄인다(별다줄)

1. 간단 설명

---

크기가 N인 수열 A가 주어진다

수열의 각 원소에 대해서 오른쪽의 수 들 중에서 가장 왼쪽에 있는 자신보다 큰 수를 구한다

2. 문제 분석

---

주의사항

제한시간은 1초, 입력은 최대 100만개의 수열이 주어진다

완전탐색

각 원소을 0번부터 N-1까지 탐색하며, 오른쪽을 탐색하는 방법

그러나 최대 원소의 개수가 100만개이므로 O(N^2)의 시간 복잡도로는 무조건 시간초과 발생

스택을 이용?

감이 안잡혀서 밑에 알고리즘 분류를 보니 스택이였다

나름 스택을 이용해서 풀이해 보려 했으나 마찬가지로 O(N^2)의 시간 복잡도를 가짐

아래 방법은 시도했던 방법이다

1. 수열을 역순으로 스택에 넣는다
2. 스택의 top을 꺼내서 다음 top과 비교
3. 더 크면 오큰수, 아니면 또 꺼내봄
	- 더큰수를 찾은 시점에서 버렸던 수들을 다시 스택에 넣는다
4. 이를 끝까지 반복한다

풀이

오른쪽에서 가장 큰 수를 찾는 문제이므로,

오른쪽부터 접근하면 쉽다

가장 최근의 큰 수를 저장(A)해두었다가, 그것보다 작은 수(B)가 나오면 무조건 NEG(B) = A이기 때문

B도 버리지 않고 스택에 저장해두어야한다

예를들어 3, 5, 2, 7 인 경우

5의 오큰수는 7, 3의 오큰수는 5이므로, 5도 기록해두어야 오큰수를 찾을 수 있다

2는 오큰수가 될 수 없으므로 스택에 저장하지 않는다

즉, 오큰수가 될 수 있는 수들만 스택에 저장해두는 것

1. 수열을 입력받는다
2. 수열의 역순으로 seq[i-1]부터 접근한다
3. 현재 스택에 내용물이 있고, 현재 top이 seq[i]보다 작다면 
	오큰수가 아니므로 뺀다
4. 더 이상 뺄 내용이 없다면 오큰수 존재X. -1 출력
5. top이 seq[i-1]보다 크면 오큰수이므로 이를 ans[i]에 저장한다
6. 3-5 과정을 반복 후, ans 배열을 출력한다

3. 소스코드

---

#include <iostream>
#include <stack>

using namespace std;

int N;
int ans[1000001], seq[1000001];
stack<int> st;


int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> seq[i];
	}

	for (int i = N - 1; i >= 0; i--) {
		// seq[i] 에 대해서 오큰수 찾기
		while (!st.empty() && st.top() <= seq[i]) {
			st.pop();
		}

		if (st.empty()) ans[i] = -1;
		else ans[i] = st.top();

		st.push(seq[i]);
	}

	for (int i = 0; i < N; i++) {
		cout << ans[i] << " ";
	}

	return 0;
}

참조

https://reakwon.tistory.com/196

https://cocoon1787.tistory.com/347