[C++] 백준 17298번 - 오큰수

 처음에는 스택, 벡터 라이브러리를 사용하지 않고 for문으로 하나씩 검사하는 알고리즘으로 코드를 작성했다.

위 코드로 채점하니까 시간 초과가 떠서 결국 구글링을 하게 됐다.

 

 구글링 한 코드를 분석하니까 벡터는 입력한 수를 저장하고 스택은 i번째 원소의 오큰수를 찾기 위해 인덱스 i를 저장한다. 두 번째 for문은 원소 개수만큼 반복한다. while문 조건은 스택이 비어있지 않고 v[s.top()]<v[i]이면(i번째 원소보다 i번째 이후의 원소가 크면 -> 오큰수를 찾으면), v[i](오큰수)를 출력할 벡터에 대입하고 스택의 top(인덱스 i)을 pop한다. while문 조건을 만족하지 못하면 스택에 i값을 push한다.(스택에 인덱스 i 삽입)

 

참고: https://sihyungyou.github.io/baekjoon-17298/

백준 17298번 : 오큰수

아래는 위 블로그를 참고해서 작성한 코드이다.

#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int main()
{
	int n, temp;
	vector <int> v;
	stack <int> s;

	scanf_s("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf_s("%d", &temp);
		v.push_back(temp);
	}

	vector <int> print(n, -1);

	for (int i = 0; i < v.size(); i++)
	{
		while (!s.empty() && v[s.top()] < v[i])
		{
			print[s.top()] = v[i];
			s.pop();
		}
		s.push(i);
	}
	for (int i = 0; i < print.size(); i++)
	{
		printf("%d ", print[i]);
	}
}

잘못된 점이 있으면 아래 댓글로 많이 남겨주세요!

감사합니다.