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

문제

문제가 너무 길어서 잘랐어요 여기만 읽어도 풀 수 있습니다.

(난이도는 실버 4)

정답 코드

#include <iostream>
#include <map>
#include <string>
#include<sstream>
using namespace std;

 map <string, int> dic;

// int s_to_num(string s)
// {
//         istringstream ss(s);
//         int x;
//         ss >> x;
//         return (x);
// }
string arr[1000000];
int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int in_num;
	int f_num;
	string s;
	cin >>  in_num >> f_num;
	for (int i = 1; i <=in_num;i++)
	{
		cin >> s;
		arr[i] = s;
		dic.insert({s,i});
	}
	for (int i=0; i < f_num;i++)
	{
		cin >> s;
		if ('0'<=s[0]&& s[0]<='9')
			cout << arr[stoi(s)] << "\n";
		else
			cout << (int)(dic.find(s)->second) << "\n";
	}
}

다른 정답코드

/*
   포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습
   입력 : 포켓몬의 개수 N ,맞춰야 하는 문제의 개수 M
          1 ~ N 포켓몬 이름, 문제 : M개 숫자는 문자로 문자는 숫자로!
   조건 :  1 <= N,M <= 100000,
   */

#include<iostream>
#include<algorithm>
#include<sstream>
using namespace std;

typedef struct mmmm
{
        string name;
        int number;
}mons;

bool sort_fuc(mons a,mons b)
{
        return (a.name < b.name);
}

bool is_num(const string& i)
{
        if ('0'<= i[0] && i[0] <='9')
                return (true);
        return (false);
}

int s_to_num(string s)
{
        istringstream ss(s);
        int x;
        ss >> x;
        return (x);
}

void find_result(mons *monster,string target,int end)
{
        int start = 0;
        int mid;
        while (start <= end)
        {
                mid = (start + end) / 2;
                if (monster[mid].name == target)
                {
                        cout << monster[mid].number << "\n";
                        return;
                }
                else if (monster[mid].name > target)
                {
                        end = mid -1;
                }
                else
                        start = mid + 1;
        }
}


int main()
{
        ios :: sync_with_stdio(0);
        cin.tie(0);
        int mon_n,matter_n;
        cin >> mon_n >> matter_n;
        mons *monster = new mons [mon_n];
        mons *monster_name = new mons [mon_n];
        for (int i = 0; i < mon_n; i++)
        {
                cin >> monster[i].name;
                monster_name[i].name = monster[i].name;
                monster[i].number = i + 1;
                monster_name[i].number =i+1;
        }
        //cout << "\n-----------------------------------------------------------\n";
        sort(monster,monster + mon_n,sort_fuc);
        string input;
        for (int i =0 ;i < matter_n; i++)
        {
                cin >> input;
                if (is_num(input))
                        cout << monster_name[s_to_num(input) - 1].name<<"\n";
                else
                        find_result(monster,input,mon_n -1);
        }
}

문제 풀이의 흐름

1. 문제에서 받는 input이 많은데 전부 map에 넣어야겠다.

2. 다만 map의 key값을 문자열로 주고 문자열 배열을 만들어서 숫자로 입력이 들어오면 배열에 있는 값을 출력 문자로 들어오게 되면 문자에 해당하는 숫자를 출력했다.

주의 할 점

이 문제는 대충 풀면 시간 초과에 걸리기 정말 쉬운 문제이다.

이전에 풀었던 문제를 다시 푸는 것인데도 이렇게 걸려버렸다.

map에 대해서 아직 잘 사용을 못해서 내가 코드를 짜면서 자꾸 헷갈려서 더 오래 걸린 문제 같다.

반성 및 고찰

너무 많이 틀렸다..

초반에 map만을 활용한 코드에서 오답이 나와서 그것을 해결하는데 너무어려움을 겪었었다.

실패코드

#include <iostream>
#include <map>

using namespace std;

map <int, string> dic;

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int in_num;
	int f_num;
	string s;
	cin >>  in_num >> f_num;
	for (int i=1;i <= in_num;i++)
	{
		cin >> s;
		dic.insert({i,s});
	}
	for (int i=0; i < f_num;i++)
	{
		cin >> s;
		if ('0'<= s[0] && s[0] <='9')
			cout << dic.at(stoi(s)) ;
		else
		{
			for (auto it : dic)
			{
				if (it.second == s)
					cout << it.first;
			}
		}
	}
}

이렇게만 해주면 시간 초과가 발생한다.

탐색을 하는 부분을 이분 탐색을 이용해서 풀어보려고 했지만 이분탐색 자체는 정렬이 되어있어야만 할 수 있는 탐색이라 이 로직에서 계속해서 실패를 했었다.

결국 공간 복잡도를 늘려서 시간 복잡도를 줄이는 방식을 사용을 했다.

stoi함수

기본적 으로 stoi가 있지만 구현할 때 더 간단한 팁이 있다.

입스트림 버퍼 활용해서 atoi함수 만들기

#include<sstream>
int s_to_num(string s)
{
        istringstream ss(s);
        int x;
        ss >> x;
        return (x);
}

istringstream이라는 타입의 객체를 생성하고 그 객체를 int 형에 넣어주면 스트림 버퍼가 알아서 int 형으로 바뀌게 된다. 사실 숫자나 문자도 스트림에서는 다 같은 존재이기때문에 그 방식을 활용한 코드이다. 물론 이 문제에서는 딱히 필요가 없는 코드이긴 하지만 쉽게 이해를 할 수 있다면 atoi함수를 매우 쉽게 구현할 수 있는 방법이다.

Uploaded by N2T