백준1620번 나는야 포켓몬 마스터 이다솜 구현해보기

---

```

백준1620번 나는야 포켓몬 마스터 이다솜 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 1620번 풀이
2.  포켓몬 마스터의 정의

---

 

 

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

1620번: 나는야 포켓몬 마스터 이다솜

백준 1620번 나는야 포켓몬 마스터 이다솜은

난이도 쉬움 등급의 문제로서

 

포켓몬 마스터가 되고 싶은 소녀가 박사님에게 포켓몬 도감을 받아서 포켓몬 정보를 입력하고 출력해 보는 문제입니다.

 

포켓몬 마스터는 포켓몬 세계관에서 세계 최강의 포켓몬 트레이너를 칭합니다.

원피스의 해적왕이나 나루토의 호카케?급 이상이라 보시면 됩니다.

 

그럼 다시 문제로 돌아와서

 

포켓몬을 제외하고

 

입력받고자 하는 스트링 데이터의 갯수 N과 출력하고자 하는 스트링 데이터의 갯수M을 첫 줄에 입력합니다.

둘째 줄부터  N개의 스트링을 입력하고

N+1 줄부터 M개의 스트링 혹은 정수를 입력합니다.

 

예를 들어 포켓몬 5마리를 넣고 2마리를 찾고자 한다면

5 2

Pikachu

Charizard

Arbok

Raichu"

Pidgey

1

Charizard

 

출력

Pikachu

2

가 나올것입니다.

 

저는 2번의 시도 끝에 구했고 첫번째 시도에서는 시간초과가 나서

편법을 썼습니다.

 

갯수가 100,000 개 이상이라는 점과 시간제한을 유의하셔서

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

일단 제 첫시도를 한번 흩어보시고

 

-1차 시도 시간초과-

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#pragma warning(disable : 4996)

// string 입력용 배열
char g_temp[25];

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

class CPockedex {
private:
	vector<string> vecPockedex;
	int pokedexSize;

public:
	CPockedex(const int pokedexSize)
	{
		this->pokedexSize = pokedexSize;
	}
	~CPockedex()
	{
		vecPockedex.clear();
	}
	
	void insertPocketMonInfo(const string poketmonName )
	{
		vecPockedex.push_back(poketmonName);
	}

	string getPocketMonInfo(int index)
	{
		return vecPockedex.at(index);
	}

	int getPocketMonInfo(string name)
	{
		int index = 0;
		for (string str : vecPockedex)
		{
			index++;
			if (name.compare(str) == 0)
			{
				return index;
			}
		}
		
		return -1;
	}

	bool is_number(const std::string& s)
	{
	//	if (s[0] != '0' &&
	//		s[0] != '1' &&
	//		s[0] != '2' &&
	//		s[0] != '3' &&
	//		s[0] != '4' &&
	//		s[0] != '5' &&
	//		s[0] != '6' &&
	//		s[0] != '7' &&
	//		s[0] != '8' &&
	//		s[0] != '9')
	//	{
	//		return false;
	//	}
	//	else
	//	{
	//		true;
	//	}
	// 
	return !s.empty() && std::find_if(s.begin(),
		s.end(), [](unsigned char c) { return !std::isdigit(c); }) == s.end();
	}
};




int main()
{
	int pockedexSize, querySize;
	scanf("%d %d", &pockedexSize, &querySize);

	CPockedex* cPockedex = new CPockedex(pockedexSize);

	for (int i = 0; i < pockedexSize; i++)
	{
		scanf("%s", g_temp);
		const string pocketmonName = g_temp;
		cPockedex->insertPocketMonInfo(pocketmonName);
	}

	for (int i = 0; i < querySize; i++)
	{
		scanf("%s", g_temp);
		const string query = g_temp;
		
		if (cPockedex->is_number(query))
		{
			int tempval = stod(query);
			printf("%s", cPockedex->getPocketMonInfo(tempval - 1).c_str());
		}
		else
		{
			printf("%d", cPockedex->getPocketMonInfo(query));
		}
	}
	return 0;
}

 

두번째 시도를 설명하겠습니다.

포켓몬 도감 클래스를 만들고

그안에 벡터와 맵을 다 넣었습니다.

왜냐하면

스트링으로 숫자를 찾을때

숫자로 스트링을 구할때 속도가 다르기 때문입니다.

또한 시간복잡도를 낮추는 대신

공간 복잡도가 늘어난 점도 유의 할 점입니다.

 

클래스는 생성자 그리고 만들다가 만 소멸자가 있으며

 

포켓몬 정보를 넣어주는 insertPocketMonInfo
포켓몬 정보를 받아오는 getPocketMonInfo
그리고 오버로딩된  getPocketMonInfo
숫자인지 스트링인지 판별해주는 is_number가 있고

 

class CPockedex {
private:
	map<string, int> mapPockedex;
	vector<string> vecPockedex;
	int pokedexSize;

public:
	CPockedex(const int pokedexSize)
	{
		this->pokedexSize = pokedexSize;
	}
	~CPockedex()
	{
	}
	
	void insertPocketMonInfo(const string poketmonName, const int poketmonIndex)
	{
		mapPockedex.insert(make_pair(poketmonName, poketmonIndex+1));
		vecPockedex.push_back(poketmonName);
	}

	string getPocketMonInfo(const int index)
	{
		return vecPockedex.at(index-1);
		//for (auto const& pocketmon : mapPockedex)
		//{
		//	if (pocketmon.second == index)
		//	{
		//		return pocketmon.first;
		//	}
		//}

		//return "";
	}

	int getPocketMonInfo(string name)
	{
		return (mapPockedex.find(name)->second);
	}

	bool is_number(const std::string& s)
	{
	//	if (s[0] != '0' &&
	//		s[0] != '1' &&
	//		s[0] != '2' &&
	//		s[0] != '3' &&
	//		s[0] != '4' &&
	//		s[0] != '5' &&
	//		s[0] != '6' &&
	//		s[0] != '7' &&
	//		s[0] != '8' &&
	//		s[0] != '9')
	//	{
	//		return false;
	//	}
	//	else
	//	{
	//		true;
	//	}
	// 
	return !s.empty() && std::find_if(s.begin(),
		s.end(), [](unsigned char c) { return !std::isdigit(c); }) == s.end();
	}
};

 

입력은 cout의 경우 느려서 시간초과가 나오기 떄문에

scanf를 사용하였으며

 

데이터를 입력받고

데이터를 출력하는 간단한 

문제입니다.

 

int main()
{
	int pockedexSize, querySize;
	scanf("%d %d", &pockedexSize, &querySize);

	CPockedex* cPockedex = new CPockedex(pockedexSize);

	for (int i = 0; i < pockedexSize; i++)
	{
		scanf("%s", g_temp);
		const string pocketmonName = g_temp;
		cPockedex->insertPocketMonInfo(pocketmonName, i);
	}

	for (int i = 0; i < querySize; i++)
	{
		scanf("%s", g_temp);
		const string query = g_temp;
		
		if (cPockedex->is_number(query))
		{
			int tempval = stod(query);
			printf("%s\n", cPockedex->getPocketMonInfo(tempval).c_str());
		}
		else
		{
			printf("%d\n", cPockedex->getPocketMonInfo(query));
		}
	}
	return 0;
}

 

 

전체코드는 다음과 같습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

#pragma warning(disable : 4996)

// string 입력용 배열
char g_temp[25];

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

class CPockedex {
private:
	map<string, int> mapPockedex;
	vector<string> vecPockedex;
	int pokedexSize;

public:
	CPockedex(const int pokedexSize)
	{
		this->pokedexSize = pokedexSize;
	}
	~CPockedex()
	{
	}
	
	void insertPocketMonInfo(const string poketmonName, const int poketmonIndex)
	{
		mapPockedex.insert(make_pair(poketmonName, poketmonIndex+1));
		vecPockedex.push_back(poketmonName);
	}

	string getPocketMonInfo(const int index)
	{
		return vecPockedex.at(index-1);
		//for (auto const& pocketmon : mapPockedex)
		//{
		//	if (pocketmon.second == index)
		//	{
		//		return pocketmon.first;
		//	}
		//}

		//return "";
	}

	int getPocketMonInfo(string name)
	{
		return (mapPockedex.find(name)->second);
	}

	bool is_number(const std::string& s)
	{
	//	if (s[0] != '0' &&
	//		s[0] != '1' &&
	//		s[0] != '2' &&
	//		s[0] != '3' &&
	//		s[0] != '4' &&
	//		s[0] != '5' &&
	//		s[0] != '6' &&
	//		s[0] != '7' &&
	//		s[0] != '8' &&
	//		s[0] != '9')
	//	{
	//		return false;
	//	}
	//	else
	//	{
	//		true;
	//	}
	// 
	return !s.empty() && std::find_if(s.begin(),
		s.end(), [](unsigned char c) { return !std::isdigit(c); }) == s.end();
	}
};




int main()
{
	int pockedexSize, querySize;
	scanf("%d %d", &pockedexSize, &querySize);

	CPockedex* cPockedex = new CPockedex(pockedexSize);

	for (int i = 0; i < pockedexSize; i++)
	{
		scanf("%s", g_temp);
		const string pocketmonName = g_temp;
		cPockedex->insertPocketMonInfo(pocketmonName, i);
	}

	for (int i = 0; i < querySize; i++)
	{
		scanf("%s", g_temp);
		const string query = g_temp;
		
		if (cPockedex->is_number(query))
		{
			int tempval = stod(query);
			printf("%s\n", cPockedex->getPocketMonInfo(tempval).c_str());
		}
		else
		{
			printf("%d\n", cPockedex->getPocketMonInfo(query));
		}
	}
	return 0;
}

 

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---