[백준] 오등큰수 (17299번)

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1 복사

7 1 1 2 3 4 2 1

예제 출력 1 복사

-1 -1 1 2 2 1 -1

---

문제에서 주어진 오등큰수의 정의에 따라 답을 구해야한다. 

스택을 이용하는 게 힌트로 주어졌기 때문에 스택을 사용했다.

스택을 사용할 땐 항상 empty인지 주의해야 한다. 스택 사용할 때 나오는 에러의 반 이상이 스택이 비어있을 경우를 생각 안했을 때 생긴다. 

우선 입력을 받으며 각 수가 몇 번 나왔는지 세어준다.

그 후 맨 뒤의 값부터 탐색하며, 스택이 비어있다면 F(A[i])를 넣어준다. 스택이 있다면 F(A[i])와 F(st.top())을 비교한다. st.top() 등장 횟수가 더 크다면 st.top()이 i번째 수의 오등큰수이다. 

F(st.top())이 F(A[i])보다 작다면 더 큰 수가 나올 때까지 스택을 pop해준다. 이런식으로 N부터 1번째 수까지 탐색하며 답을 구한다.

 

맨 처음 등장 횟수를 셀 때 map을 이용했는데, 시간초과가 떴다. N이 그리 크지 않으니 배열을 선언해 직접 갯수를 세어주면 시간 내에 해결할 수 있다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%98%A4%EB%93%B1%ED%81%B0%EC%88%98%20(17299%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
int N;
vector<int> v;
vector<int> res;
int m[1000001];
stack<int> st;

int main() {

	cin >> N;
	v.resize(N + 1);
	res.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> v[i];
		m[v[i]]++;
	}

	for (int i = N; i >= 1; i--) {
		if (st.empty()) {
			st.push(v[i]);
			res[i] = -1;
		}
		else if (m[v[i]] < m[st.top()]) {
			res[i] = st.top();
			st.push(v[i]);
		}
		else {
			while (!st.empty() && m[v[i]] >= m[st.top()]) {
				st.pop();
			}
			if (st.empty()) {
				res[i] = -1;
				st.push(v[i]);
			}
			else {
				res[i] = st.top();
				st.push(v[i]);
			}
		}
	}

	for (int i = 1; i <= N; i++)
		cout << res[i] << " ";
}