문제
문제가 너무 길어서 잘랐어요 여기만 읽어도 풀 수 있습니다.
(난이도는 실버 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);
}
}문제 풀이의 흐름
- 문제에서 받는 input이 많은데 전부 map에 넣어야겠다.
- 다만 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