글 읽기 - 메모리 초과 도와주세요!

shrimp1998 3년 전 0

postorder의 경우 루트가 마지막 원소이니까 그 원소를 찾고 inorder에서 좌 우로 나누어 재귀적으로 구현했습니다. 그런데 18%에서 메모리 초과가 계속

뜹니다. 제 생각에는 함수의 재귀가 깊어져서 뜨는 건가? 싶지만 잘 모르겠습니다. 다른 분들의 풀이를 보니 vector의 포인터를 주지 않고 그냥 인덱스로 푸는 것 같습니다.

#include <algorithm>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <stack>	
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <list>
#define For(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

vector<int> in, post;

vector<int> slice(const vector<int>& vec, int start, int end) {
	return vector<int> (vec.begin() + start, vec.begin() + end);
}

void preOrder(const vector<int>& in, const vector<int>& post) {
	int size = in.size();
	if (in.empty()) return;
	int root = post.back();
	int L = find(in.begin(), in.end(), root) - in.begin();
	int R = size - L - 1;
	cout << root << " ";
	preOrder(slice(in, 0, L), slice(post, 0, L));
	preOrder(slice(in, L + 1, size), slice(post, L, size - 1));
}

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

	int num;
	cin >> num;
	in.resize(num);
	post.resize(num);
	For(i, num) cin >> in[i];
	For(i, num) cin >> post[i];
	preOrder(in, post);
}

bupjae 3년 전 1

slice 함수에서 새로운 vector 를 만들어서 값을 복사하고 있습니다.

최악의 경우 (n = 100000 이고, 트리의 모양이 linked list 처럼 생겼을 때)

입력으로 100000 크기의 vector 2개 생성

-> 첫 번째 호출에서 99999 크기의 vector 2개 상성

-> 두 번째 호출에서 99998 크기의 vector 2개 생성 -> ......

이런식으로 진행하기 때문에 공간복잡도가 O(n^2) 이 됩니다.

vector 전체를 복사하는 대신 index 만 넘겨주는 식으로 수정하면 메모리 초과 없이 통과할 수 있을 겁니다.

shrimp1998 3년 전 0

bupjae님 감사합니다!!! 댓글처럼 트리가 비효율적으로 주어지면 벡터가 엄청나게 많이 늘어나네요.. 함수를 벡터의 참조자로 주지 않고 각 벡터의 시작 인덱스와 끝 인덱스를 주는 형식으로 풀었습니다!

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

문제

문제

출처

ICPC

메모리 초과 도와주세요!

shrimp1998 3년 전 0

bupjae 3년 전 1

shrimp1998 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말