글 읽기 - 런타임 에러나는 이유를 알 수 있을까요?

lch32111 5년 전 0

알고리즘이 맞고 문제 없이 짰다고 생각하는데, 계속해서 런타임 에러가 뜨네요.

혹시 코드에서 문제점 알려주실 수 있을까요?

알고리즘은

중위순회 하듯이 linked list로 트리를 만들고나서, X와 Y에 해당되는 노드를 찾아서

한 쪽 노드 기준으로 dot flag를 true로 만들면서 트리의 root까지 dot flag를 true로 만들어줍니다.

그리고 다른 쪽 노드의 dot flag가 true랑 만나는 점은 LCA(최소 공통 조상)를 발견한걸로 보아 그 노드를

return합니다. 그 노드는 들어올 때 index와 나가는 index가지고 있어서 그것을 출력하면 되고요.

소스코드에 주석으로 이해 되게끔 달아 놓았습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <map>
#include <cmath>
#include <queue>
#include <functional>
#include <vector>

using namespace std;


#define intmax 2147483647
// 반복문에 REP을 쓰니 한 번 봐주세요
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define max(a,b) (a>b ? a : b)
#define mp make_pair
#define SIZE 4000

// linked list tree의 node의 data에 들어갈 자료구조
class info
{
public:
	int data; // 각자의 노드를 식별하기 위한 데이터
	int in_index; // binary에서 node를 push 할 때의 index
	int out_index; // binary에서 node를 거슬러 올라갈 때의 index

	friend bool operator<(const info& left, const info& right)
	{
		return left.data < right.data;
	}

	friend bool operator==(const info& left, const info& right)
	{
		return left.data == right.data;
	}

	friend bool operator!=(const info& left, const info& right)
	{
		return left.data != right.data;
	}
};

// node 자료구조
struct node
{
	info data;
	bool dot; // LCA를 위해 지나간 길을 표시하기 위함.
	node* parent;
	node* left;
	node* right;
};

// 트리 자료구조
class tempTree
{
public:
	node* root;
	node* cursor; // 현재 point하고 있는 노드

	tempTree() : root(NULL), cursor(NULL) {}
	~tempTree()
	{
		allDelete(root);
	}
	void allDelete(node* _node)
	{
		if (_node->left != NULL)
			allDelete(_node->left);
		if (_node->right != NULL)
			allDelete(_node->right);

		delete _node;
	}

    // 왼쪽 방향으로 넣기 
	void leftInsert(const info& data)
	{
        // cursor == NULL이란 것은 root가
        // 없다는 것으로, 처음 root에 data를 넣어주고
        // cursor가 root를 받도록 함.
		if (cursor == NULL)
		{
			root = new node();
			root->data = data;
			root->dot = false;
			root->left = NULL;
			root->right = NULL;
			root->parent = NULL;

			cursor = root;
			return;
		}

		node* temp = new node();
		temp->data = data;
		temp->dot = false;
		temp->left = NULL;
		temp->right = NULL;
		temp->parent = cursor;

        // cursor는 항상 들어온 것을 가리키고 있음.
		cursor->left = temp;
		cursor = temp;
	}

	void rightInsert(const info& data)
	{
		node* temp = new node();
		temp->data = data;
		temp->dot = false;
		temp->left = NULL;
		temp->right = NULL;
		temp->parent = cursor;

		cursor->right = temp;
		cursor = temp;
	}

    // 1이 나오면 이 함수를 실행시켜, 현재 커서의 부모로 올라감
	void GoupCursor()
	{
		cursor = cursor->parent;
	}

	node* getCursor()
	{
		return cursor;
	}

	info* getCursorData()
	{
		return &cursor->data;
	}

    // 트리구조를 형성하고 나서 value에 해당하는 노드를 찾기 위한 함수
	node* find(const info& value)
	{
		return getNode(root, value);
	}

    // 재귀로 해당 노드를 찾습니다.
	node* getNode(node* _node, const info& key)
	{
		if (_node->data == key)
			return _node;

		node* left = NULL;
		node* right = NULL;
		if (_node->left != NULL)
			 left = getNode(_node->left, key);

		if (_node->right != NULL)
			right = getNode(_node->right, key);

		if (left != NULL && left->data == key) return left;
		if (right != NULL && right->data == key) return right;
		return NULL;
	}

    // LCA를 구하는 함수
	info* findSubTreeParent(const info& left, const info& right)
	{
        // 해당 노드 찾기
		node* left_node = find(left);
		node* right_node = find(right);

        // left_cursor로 해당 노드부터 root까지 모든 부모에
        // dot flag를 true로 해줌.
		node* left_cursor = left_node;
		while (left_cursor != NULL)
		{
			left_cursor->dot = true;
			left_cursor = left_cursor->parent;
		}

		node* right_cursor = right_node;
        // right_cursor의 dot이 true라는 말은 
        // left_node와 right_node가 처음 만나는 부분으로
        // LCA이다.
		while (right_cursor->dot == false)
			right_cursor = right_cursor->parent;

		return &right_cursor->data;
	}
};

int N;
string antbinary;
bool ant[SIZE];
int X, Y;

tempTree myBST;

int ans_left, ans_right;

void TakeInput()
{
	cin >> N;
	
	cin >> antbinary;
	REP(i, antbinary.size())
		ant[i] = antbinary[i] - '0';
	cin >> X >> Y;
}

void Solve()
{
#define PUSH 0
#define ESCAPE 1
	int StandardValue = 0;
	int XValue = 0;
	int YValue = 0;
	REP(i, antbinary.size())
	{
		bool operation = ant[i];
		if (operation == PUSH)
		{
            // 노드값 식별을 위해 1씩 증가된 값을 넣어줌.
			StandardValue += 1;

			info temp;
			temp.data = StandardValue;
			temp.in_index = i + 1; // push하는 index
			temp.out_index = -1;

			node* cursor = myBST.getCursor();

            // cursor가 NULL이면, 새로 만들어야 되어서 그대로
            // left insert
			if (cursor == NULL)
				myBST.leftInsert(temp);
            // left가 비어있으면 먼저 left에 넣는다.
			else if (cursor->left == NULL)
				myBST.leftInsert(temp);
            // 마지막으로 right에 넣는다.
			else if (cursor->right == NULL)
				myBST.rightInsert(temp);

            // X, Y 인덱스에 해당하는 값을 찾아서 넣기
			if (i == X - 1)
				XValue = StandardValue;
			if (i == Y - 1)
				YValue = StandardValue;
		}
		else if (operation == ESCAPE)
		{
			info* find = myBST.getCursorData();
			find->out_index = i + 1; // push하는 index
			myBST.GoupCursor(); // parent로 cursor 옮기기

			if (i == X - 1)
				XValue = find->data;
			if (i == Y - 1)
				YValue = find->data;
		}
	}

	info temp1; temp1.data = XValue;
	info temp2; temp2.data = YValue;
    // LCA 찾기
	info* parent = myBST.findSubTreeParent(temp1, temp2);
    
    // LCA의 들어온 index, 나간 index 넣어서 출력
	ans_left = parent->in_index;
	ans_right = parent->out_index;
}

void Print()
{
	cout << ans_left << ' ' << ans_right;
}

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

	TakeInput();
	Solve();
	Print();

	return 0;
}

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

문제

문제

출처

ICPC

런타임 에러나는 이유를 알 수 있을까요?

lch32111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말