[Beakjoon Online Judge] 1620 - 나는야 포켓몬 마스터 이다솜

• I 문제 소개

• II 문제 풀이
• 0. 초기 환경 설정
• 1. 도감 입력
• 2. 도감 출력
• 3. 시간 극한으로 줄이기
• 4. 최종

• III 느낀점

I 문제 소개

---

문제

안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어.
(뚜벅 뚜벅)
얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~
(펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ
(터벅터벅)
어? 누구지?

...
...
(내용이 너무 길고 변태 같아서 중간 생략합니다)
...
...

이다솜 : 휴... 이겼다.
오영식 : 내가 지다니 분하다. ㅜㅜ
오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

 

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

 

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

---

II 문제 풀이

---

옛날 옛적에 닌텐도DS로 포켓몬스터DP를 하던 시절을 떠올리며 들어간 문제인데,

문제가 너무 변태같아서 포기할까도 했지만 사실 물어보는 것만 보면 별 게 없는 문제라 일단 풀었다.

 

간단히 요약하자면, 숫자 - 문자열이 대응된 포켓몬 도감에 숫자를 입력하면 문자열이, 문자열을 입력하면 숫자가 출력되게 하면 되겠다.

 

어느정도 예상했다시피 이 문제는 시간을 굉장히 까다롭게 주기 때문에 정말 극한의 극한까지 시간을 줄여야한다. 그래서 여러가지 방법을 총동원했다.

 

0. 초기 환경 설정

---

#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main(void)
{
	unordered_map<string, int> pokemon;
	string pokemon2[100001];
	string str;
	
	int M, N;
	cin >> N >> M;

	return 0;
}

맵도 그냥 맵이 아니라 해시맵을 사용했는데, 연산이 단순하고 데이터가 방대해질수록 해시맵이 빠르다고 해서 사용했는데 맵을 해도 되는지는 안해봐서 잘 모르겠다. (C++에서는 해시맵이 unordered_map이다!)

 

나는 시간 효율 > 메모리 효율로 판단해서, 문자열로 호출할 땐 맵을 이용하고 숫자로 호출할 땐 배열을 이용해 풀었다. 처음에는 맵 하나로 key로 탐색(은 그냥 호출하면 됨) / value로 탐색하는 것을 구현하려고 했는데, 이렇게 하면 정렬 / 탐색을 굳이 구현하지 않아도 복잡도가 어느정도 보장되면서 편하게 할 수 있어 이렇게 했다.

 

1. 도감 입력

---

for (int i = 1;i <= N;i++)
{
	cin >> str;
	pokemon[str] = i;
	pokemon2[i] = str;
}

그냥 단순하게 str을 받는데, 입력이 도감의 순서대로 주어진다고 해서 그냥 그대로 배열과 해시맵에 넣었다.

 

2. 도감 출력

---

for (int i = 0;i < M;i++)
{
	cin >> str;
	if (str[0]>='0'&&str[0]<='9')
		cout << pokemon2[atoi(str.c_str())] << endl;
	else
		cout << pokemon[str] << endl;
}

포인트라고 할 수 있다면 들어온 입력이 숫자인지 문자열인지 무차별로 주어지기 때문에, 구분을 해줘야했는데 이 때 isdigit이라는 함수를 써서 판별할 수도 있었으나 뭔가 더 오래걸릴 것 같은 느낌에, 문제에서 준 문자열은 문자로만 이루어져있다는 특성을 이용해 쉽게 첫 글자가 0과 9 사이면 숫자임으로 판단했다.

 

3. 시간 극한으로 줄이기

---

사실 위처럼 코드를 작성해도 시간초과가 뜬다. 이를 해결하기 위한 방법 중 하나는, C++의 특성을 이용하는 방법이 있다.

 

C의 입출력 방식인 scanf / printf은 충분히 빠른 속도이나, C++의 입출력 방식인 cin / cout는 느린 방식이라 시간 초과가 날 수 있다. 이를 C++ 차원에서 해결하려면, 아래 세 개를 이용하면 된다.

1. 개행을 할 때 endl 대신 '\n'을 사용한다.
    - endl은 개행을 하면서 출력 버퍼를 비우는 기능까지 있어 느리다.

2. cin.tie(NULL)으로 cin과 cout의 묶음을 풀어 준다.
    - cin에도 출력 버퍼를 비우는 기능이 있어 느린데, 이걸 이용하면 그러지 않는다.

3. ios_base::sync_with_stdio(false)를 사용한다.
    - 코딩 좀 했다면 C++ iostream에서 C에 있는 함수도 사용할 수 있다는 것을 알 것이다. 그 관계를 끊어준다.
    - 단, 이걸 쓰면 그 코드에선 cin cout를 printf scanf gets 등등과 같이 사용하면 안된다.

 

4. 최종

---

#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	unordered_map<string, int> pokemon;
	string pokemon2[100001];
	string str;
	
	int M, N;
	cin >> N >> M;

	for (int i = 1;i <= N;i++)
	{
		cin >> str;
		pokemon[str] = i;
		pokemon2[i] = str;
	}
    
	for (int i = 0;i < M;i++)
	{
		cin >> str;
		if (str[0]>='0'&&str[0]<='9')
			cout << pokemon2[atoi(str.c_str())] << '\n';
		else
			cout << pokemon[str] << '\n';
	}
	return 0;
}

 

극한의 극한까지 시간을 줄였다.

 

생각해보면 별 거 없는 문제인데, 시간을 줄이는 방법에 있어서 정답률이 꽤 낮은 문제인 것 같다.

 

III 느낀점

---

사실 이런류의 문제는 아름답지 않아서 좋아하지 않는 편이다. 수학 문제로 치면 별거 없는 계산 문제인데 괜히 소숫점 20자리까지 계산해야하고 반올림해야하는 느낌?

여튼 이런 문제는 문제의 본질을 푸는 것 보다는 문제를 위한 문제 그런 것이어서 이것은 백준에 있는 문제이기에 아래 사이트들에 있는 내용이 도움이 많이 되었다.

 

 

www.acmicpc.net/blog/view/55

자주 틀리는 요인

www.acmicpc.net/blog/view/70

BOJ 101

www.acmicpc.net/problem/15552

15552번: 빠른 A+B

www.acmicpc.net/board/view/22716

글 읽기 - 추가 설명 및 다른 언어 빠른 입출력 방법

 

Coding Space by MIR :

Beakjoon Online Judge 1620번 나는야 포켓몬 마스터 이다솜 C++

BOJ 1620번 나는야 포켓몬 마스터 이다솜 C++

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