[백준/C++] 오등큰수

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 오큰수 문제와 크게 다른게 없다.

 

오큰수 문제 풀이

 

오큰수가 오른쪽에 있는 수 중에서 크면서 가장 가까운 수를 찾는 문제였다면, 오등큰수 문제는 등장하는 횟수를 비교하는 문제다.

 

즉, 비교하는 게 숫자의 크기가 아니라 등장횟수로 바뀐 것 뿐인 문제다.

 

처음에 문자가 몇 번 등장했는지를 map이나 array를 이용해 기록한다.

 

이후 순차적으로 숫자를 비교해 등장 횟수가 i번 째 수보다 큰지 비교하면 된다.

만약 i번째 수와 같거나 작다면 stack에 i번째 숫자를 기록한다. (stack에 i번째 수 추가)

 

마찬가지로 stack구조를 이용하면 문제를 쉽게 풀 수 있기 때문에 stack을 사용해 숫자를 기록했다.

 

 

 

​

[아이디어 정리]

1. 숫자의 등장 횟수를 unordered_map이나, array에 기록한다.
2. i번째 수가 등장하면 이전에 기록된 숫자의 등장횟수와 i번째 수의 등장 횟수를 비교한다.
3. i번째 수의 등장 횟수가 크면 이전에 기록된 숫자의 오등큰수 이므로 stack에서 제거하고, i번째 수를 오등큰수로 기록한다.
4. 만약 i번째 수의 등장 횟수가 작다면, 아직 오등큰수가 등장하지 않았으므로 i번째 수를 stack에 추가한다.
5. 계산된 오등큰수를 출력한다.

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

int mm[1000000];
int number[1000000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector<int> ans(n, -1);
	stack<pair<int, int>> st;
	pair<int, int> np; //value, index
	//unordered_map<int,int> mm;
	for (int i = 0; i < n; i++)
	{
		cin >> number[i];
		mm[number[i]] += 1;
	}
	int a;
	for (int i = 0; i < n; i++) 
	{
		a = number[i];
		if (st.empty())
		{
			st.push(make_pair(a, i));
		}
		else
		{
			np = st.top();
			while (mm[a] > mm[np.first])
			{
				st.pop();
				ans[np.second] = a;
				if (st.empty())
				{
					break;
				}
				np = st.top();

			}
			st.push(make_pair(a, i));
		}
	}

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

	return 0;
}

 

---

처음에 map을 썼더니 시간 초과가 났다. 아무래도 map은 정렬을 하는 과정이 있기 때문에 시간 초과가 난 것 같다.

그래서 unordered_map을 사용했더니 문제가 풀렸다.

또 unordered_map과 vector 대신 크기가 정해진 array를 사용했더니 속도가 더 빨라졌다.

은근 속도 차이가 많이 나네...

17299번: 오등큰수