백준 c++백준 1620번 포켓몬마스터 이다솜

/*
   포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습
   입력 : 포켓몬의 개수 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);
        }
}

일단 문제가 더럽게 길었는데 서론은 아에 필요없는 내용이었다. 정성이 가득한 문제랄까

sort의 3번째 인자의 성질

이 문제를 풀면서 특별하게 더 봤던 부분이 있는데 일단 정렬을 할때 sort 함수는 true일때는 안 바꾸고 false 일때 바꾼다는 점을 기억해야하고

​

입출력 속도 늘리기

ios :: sync_with_stdio(0);

이 부분은 c와 c++의 출력 스트림을 굳이 동기화 하지 않아서 빠르게 하는 코드가 필요했다. 사실 이걸 쓰기전에 시간초과가 나서 문제가 있었다.

cin(0); 이부분은 cout과 cin사이에서 버퍼를 비워주는 작업을 원래 입력이 꼬이지 않게 하기위해서 있는데 그 부분을 생략해서 시간 복잡도를 줄이는 힘을 가졌다.

​

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

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

바로 이부분인데, #include<sstream> 안에 있고 istringstream이라는 타입의 객체를 생성하고 그 객체를 int 형에 넣어주면 스트림 버퍼가 알아서 int 형으로 바뀌게 된다. 사실 숫자나 문자도 스트림에서는 다 같은 존재이기때문에 그 성질을 활용해서 문제를 해결해봤다.

​

문제 해결방법

구조체를 처음에 생각하지 않고 그냥 배열로 풀려고 했고 2개의 구조체 배열이 아니여서 그걸 생각해 내는데 시간이 조금 걸렸다.

이분탐색을 사용했고, 그걸 이용해서 쉽게 문제를 해결 할 수 있었다.

이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.