글 읽기 - c++ 이방법으로 시간을 좀 더 줄일수 있을까요?

ahj6377 3년 전 0

잘 가다가 중간에 시간초과로 막힙니다... 스택 파트 문제길래 스택개념을 이용했는데 혹시 스택을 다른 방법으로 활용해야할까요?
스

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

int seq[1000001];
int stk[1000001];
int top = 1;
int str[1000001];
int main()
{

	int a;
	cin >> a;
	int mx = 0;
	for (int i = 1; i <= a; i++)
	{
		int b;
		cin >> b;
		seq[i] = b;
		mx = max(mx, b);
	}
	top = 0;
	int value;
	for (int i = a; i >= 1; i--)
	{
		value = seq[i];
		stk[++top] = seq[i];
		int t = top;
		if (seq[i] == mx)
		{
			str[i] = -1;

		}
		else 
		{
			while (t)
			{
				if (seq[i] < stk[t])
				{
					str[i] = stk[t];
					break;
				}
				t--;
			}
			if (t < 1)
				str[i] = -1;
		}
	}

	for (int i = 1; i <= a; i++)
		printf("%d ", str[i]);
	return 0;

}

nahwasa 3년 전 0

현재로썬 스택개념을 활용하셨다고 보기 힘듭니다.

그냥 stk이란 이름의 배열에 넣어놓고 직접 순회하며 찾고계신거죠. (N번에 대해 각각 최대 N회 찾아야하므로 O(N^2))

힌트를 드리자면 매번 stk 전체를 볼게 아니라, 시간을 줄이기 위해 stk에서 각 경우 배제할 수 있는건 배제해야 합니다.

'오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽'

부분을 잘 생각해보세요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 이방법으로 시간을 좀 더 줄일수 있을까요?

ahj6377 3년 전 0

nahwasa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말