[백준/C++] 오큰수

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 i번째 숫자의 오른쪽에 있는 수 중에서 가장 왼쪽에 있는 수를 찾으면 되는 문제다.

 

즉, i번째 수가 오면 그 수를 기준으로 오른쪽에 큰수가 나오는지 탐색을 하면 되는 문제다.

 

여기서 문제를 풀 때, 만약 i번째 수마다 오른쪽을 탐색하면 O(n^2)의 시간복잡도가 걸리게 된다.

 

대신 빠르게 푸는 방법이 있다.

 

아래 그림과 같이 3, 5, 2, 7의 4개의 숫자의 수열을 예로 들어보자.

 

처음에 3이라는 숫자가 들어오면 기록을 한다.

 

아직까지는 3의 왼쪽에 어떤 숫자가 오는지 모른다.

 

이후 들어오는 숫자는 5다.

여기서 5는 3보다 크기 때문에, 3은 자신보다 오른쪽에 있는 큰 수를 발견한다.

 

그러므로 3의 자리에는 5를 기록하고 3을 제거한다. 남은 수가 없으므로 5를 기록을 한다.

 

마찬가지로 진행을 하면

​

2는 5보다 작으므로 오른쪽에 아직 큰 수가 들어오지 않았다.

 

2를 5 다음에 기록하고, 다음에 올 수를 비교한다.

 

다음에 오는 수는 7 이다. 

여기서 7은 2보다 크므로 2에는 7을 기록하고 2를 제거한다.

 

또한 7은 5보다 크므로 5에도 7을 기록하고 5를 제거하면 된다.

 

남은 기록된 숫자가 없으므로 7을 기록하면 된다.

 

위 과정에서 숫자들의 기록은 후입선출 구조와 비슷하다.

 

그러므로 stack을 이용해 수를 기록해 문제를 풀면 된다. 

 

 

[아이디어 정리]

1. for문으로 0번째 수 부터 n번째 수까지 탐색을 시작한다.
2. i번째 수가 들어오면 이전에 기록된 숫자가 있는지 확인하고, 있다면 크기를 비교해 i번째 수가 이전에 기록된 수의 오큰수가 될 수 있는지 판단한다.
3. 만약 i번째 숫자가 기록된 숫자들의 오큰수가 되지 않는다면 i번째 수를 기록한다. (큰 수 부터 쌓여 맨 위에 작은 수가 위치하게 된다.)
4. n번째 수 까지 위 과정을 반복하고, 기록된 오큰수를 출력한다.

 

 

Code

 

 

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> ans(n, -1);
	stack<pair<int, int>> st; 
	pair<int, int> np; //value, index
	int a;
	for (int i = 0; i < n; i++) 
	{
		cin >> a;
		if (st.empty()) 
		{
			st.push(make_pair(a, i));
		}
		else 
		{
			np = st.top();
			while (a > 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;
}

 

---

Stack의 구조와 수를 기록하고 제거하는 과정이 비슷해 Stack을 활용하면 쉽게 풀 수 있는 문제다.

 

17298번: 오큰수