C++ 나는야 포켓몬 마스터 이다솜 - (STL 사용하지 않고 풀기) - 백준 알고리즘

1620번 나는야 포켓몬 마스터 이다솜 - (STL 사용하지 않고 풀기)

---

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

struct Node
{
	string data;      // 포켓몬 이름
	int id;            // 포켓몬 이름에 해당하는 ID
	Node* left;         // left child
	Node* right;      // right child
};

Node* root = NULL;    // 초기값
Node* search(string item);    // search
void insert(string item, int num);    // bst를 구성하기 위한 insert

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

	int N, M;
	string data;
	vector<string> v;   // 숫자가 입력으로 왔을 때 이름 찾는 용도

	cin >> N >> M;

	v.resize(N + 1);	// vector size 설정
	for (int i = 1; i <= N; i++)	// vector v 초기화
		v[i] = '0';

	for (int i = 1; i <= N; i++)   // 입력 받기
	{
		cin >> data;
		insert(data, i);	// data와 id를 추가
		v[i] = data;		// 찾을 때 숫자가 입력으로 받을경우 출력하기 위해서 설정
	}

	for (int i = 0; i < M; i++)      // 질문 받기
	{
		char name[20] = {'0'};	//	포켓몬 이름은 20자를 넘지 않는다고 했으므로
		string full_name;

		cin >> full_name;
		strcpy(name, full_name.c_str());	// string을 char로 변환

		if (isalpha(name[0])) //name이 알파벳이면 1반환(대문자) 아니면 0반환
		{
			cout << search(full_name)->id << "\n";
		}
		else    // 숫자인 경우
		{
			cout << v[stoi(full_name)] << "\n";
		}

	}

	return 0;
}


Node* search(string item)
{
	Node* x = root;      // root를 가리키는 x

	while (x != NULL && x->data != item)   // data가 있는 경우 and data가 item이 아닌 경우
	{
		if (item < x->data)   // 찾으려는 item이 x보다 작으면 왼쪽 child로 보냄
			x = x->left;
		else
			x = x->right;   // 아니면 오른쪽으로
	}
	return x;
}

void insert(string item, int num)	// item과 num을 추가
{
	Node * x, *y;
	Node* ins;

	ins = new Node;					// 할당
	ins->data = item;				// 입력받은 item을 data에 저장
	ins->id = num;					// 입력받은 num을 id에 저장
	ins->left = ins->right = NULL;	// ins의 left와 right를 NULL

	y = NULL;
	x = root;
	while (x != NULL)				// x가 NULL이 될 떄까지 값이 작은지 큰지를 비교하면서 넣을 공간을 찾음
	{
		// find y, the parent of ins
		y = x;
		if (ins->data < x->data)	// x보다 작으면 left로 이동
			x = x->left;
		else                        // x보다 크면 right로 이동
			x = x->right;
	}

	if (y == NULL)      // the tree was empty
		root = ins;
	else if (ins->data < y->data)
		y->left = ins;
	else
		y->right = ins;
}

---

다음 포스팅은 STL인 map을 사용하여 풀어도보도록 하겠습니다.

• 나는야 포켓몬 마스터 이다솜 - (문제 소개)

• STL map 사용하여 풀기