[2493] 탑, c++

한줄 후기 : 하.. ㅈㄴ쉬워보여서 했는데... 시간초과 죽인다.

 

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

2493번: 탑

 

자신의 왼쪽에 더 큰 값이 있다면 그 값의 인덱스를 출력하면 됨. 만약 큰 값이 없다면 0 출력

개쉬워보이는 스택문제여서 도전 후 시간초과 2번 받고 성공 ^^

완전탐색 + 스택쓰면 절대 안된다. 

테스트 케이스가 500000까지 나와서 시간초과...

받을 때 마다 조건 검사하고 스택에 추가하든 출력하든 해야 된다.

 

#include <iostream>
#include <stack>
using namespace std;
stack<int> s;
stack<int> input;
int main(){
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		int num;
	    scanf("%d", &num);
		if(s.empty())	{
			input.push(num);
			s.push(i);
			printf("0 ");
		}

		else{
			if(input.top() > num){
				int a = s.top();
				printf("%d ", a);
				s.push(i);
				input.push(num);
			}
			else{
				s.pop();
				input.pop();
				while(!s.empty()){
					if(input.top() > num){
						printf("%d ", s.top());
						s.push(i);
						input.push(num);
						break;
					}
					else{
						s.pop();
						input.pop();
					}
				}
				if(s.empty())	{
					printf("0 ");
					s.push(i);
					input.push(num);
				}
			}
		}
	}
}