글 읽기 - 스택

chanugod 7년 전 0

나름 스택으로 한다고 했는데, 잘 안되네요.. 시간초과가 뜹니다.

O(n)으로 할 수 있는 힌트를 부탁합니다.

#include <stdio.h>
#include <iostream>
using namespace std;
long long int A[500100];
int B[500100];
int stack[500100];
int main(){
	int n;
	cin >> n;
	int top ;
	int stacktop = 0;
	int x;
	int temp;
	for (int i = 1; i <= n; i++){
		cin >> A[i];
		if (A[i] >= A[stack[stacktop]])
			stack[++stacktop] = i;
		x = stack[stacktop];
		for (temp = i-1; temp>=x;temp-- ){
			if (A[i] <= A[temp]){
				B[i] = temp;
				break;
			}
		}

	}
	for (int i = 1; i <= n; i++)
		printf("%d ", B[i]);
}

jumpingz 7년 전 0

B 배열에 인덱스 정보를 저장하는 용도로 사용하신거 같은디.. 구조체 배열을 이용하여 모든 정보를 한번에 저장하고

현재 데이터가 스택에 있는 데이터보다 큰 동안 Pop 후

Top 이 비어있다면 0을 출력

아니라면 Top 의 index 값을 출력하도록 하시면 아마 TLE 는 없을꺼에요

chanugod 7년 전 0

이렇게 해봤는데 왜 m이 안받아질까요?? ㅠㅠ

#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;
int ans[500100];
int main(){
	int n;
	cin >> n;
	int m = 0;
	stack<int> a;
	stack<int> index;
	scanf("%d\n", &m);
	a.push(m);
	index.push(1);
	ans[1] = 0;
	for (int i = 2; i <= n; i++){
		scanf("%d ", &m);
		while (m>a.top()){
			a.pop();
			index.pop();
		}
		if (a.empty())
			ans[i] = 0;
		else{
			ans[i] = index.top();
		}
		a.push(m);
		index.push(i);
	}
	for (int i = 1; i <= n; i++){
		printf("%d ", ans[i]);
	}
}

jumpingz 7년 전 0

입력이 안받아지는 이유는 중간에

while (m>a.top()){
            a.pop();
            index.pop();
        }

이 영역에서 만약 top 이 널이면 비교가 불가능해서 에러가 발생해서 그렇구요.. scanf 에 존재하는 \n 와 공백은 문제가 있는건지는 모르겟네요

비쥬얼에서 디버깅했을 때는 입력시 문제가 좀 있긴하던데.. 일단 젤 중요한 부분은 저 와일문에 상위에 조건이 하나 더필요하겟네요

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

문제

문제

출처

ICPC

스택

chanugod 7년 전 0

jumpingz 7년 전 0

chanugod 7년 전 0

jumpingz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말