[PS 풀이] 백준 문제 풀이 - 17298 오큰수

👩🏻‍💻 문제링크

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

17298번: 오큰수

 

✍️ 아이디어

1. 문제 이해

• 처음엔 스택을 이용하긴 했지만 시간복잡도가 O(N^2)이 나왔다
• 결국 다른 사람이 문제푼 원리를 보고 O(N)으로 만들었다

2. https://cocoon1787.tistory.com/347 (이 블로그를 보고 아이디어를 얻음)

[C/C++] 백준 17298번 - 오큰수 (스택)

 

✍️소스코드

• 처음 틀린 내 답변

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

int main()
{
	int N; cin>>N;
	int arr[N+1]={0};
	stack <int> s; 
	stack <int> temp;
	vector <int> result;
	int value;
	
	for(int i=1; i<N+1; i++)
	{
		cin>>arr[i];
		s.push(arr[i]);
	}
	
	for(int i=1; i<N+1; i++)
	{
		temp=s;
		value = -1;
		while(temp.size() != i)
		{
			if(temp.top() > arr[i])
			{
				value=temp.top();
			}
			temp.pop();
		}
		result.push_back(value);
	}
	
	for(auto iter=result.begin(); iter!=result.end(); iter++)
	{
		cout<<*iter<<" ";
	}
}

 

 

 

<고친 답변> : 뒤에서부터 오큰수를 찾는 방식 + 오큰수를 스택에 저장함

 

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

	
stack <int> s; 
int main()
{
	cin.tie(NULL); cout.tie(NULL);
	ios::sync_with_stdio(false);
	int arr[1000002];
	int result[1000002];
	int N; 
	cin>>N;
	for(int i=1; i<N+1; i++)
	{
		cin>>arr[i];
	}
	
	for(int i=N; i>0; i--)
	{
		while(!s.empty() && s.top()<arr[i])
			s.pop();
		if(s.empty())
			result[i]=-1;
		else
			result[i]=s.top();
		s.push(arr[i]);
	}
	
	for(int i=1; i<N+1; i++)
	{
		cout<<result[i]<<" ";
	}
}

 

체감난이도	걸린시간	참고	사용 문법
상	1H	아이디어 참고	스택

 

 

 

 

<다른 답변> : 오큰수가 나올때까지 스택에 인덱스를 쌓는 방식

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

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int n;
	cin >> n;
	
	vector<int> arr(n + 1);
	stack<int> st;
	vector<int> nge(n + 1, -1);

	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}

	for (int i = 1; i <= n; i++)
	{
		while (!st.empty() && arr[st.top()] < arr[i])
		{
			nge[st.top()] = arr[i];
			st.pop();
		}
		st.push(i);
	}

	for (int i = 1; i <= n; i++)
	{
		cout << nge[i] << ' ';
	}
	cout << '\n';
}

 

✍️알아야 할점

1. 스택 + 배열에서 시간복잡도가 O(N)이 나올려면 배열이 지나가면서 스택에 넣고 스택이 정리 되어야 함