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

문제

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

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

문제 풀이

이 문제는 Map 혹은 Hash로 아주 쉽게 풀 수 있다.

 

C++ Map 사용법

https://go-jowick.tistory.com/15

C++ STL Map 사용법

하나의 맵과 하나의 string 배열을 만들어 입력을 받아 각각 저장을 시켜주어 출력을 시키면 된다.

 

전체 코드

#include <bits/stdc++.h>
#include <string>

using namespace std;

int main(){

        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int N, M;

        cin >> N >> M;

        map<string, int> input;
        string name[100001];

        string temp;

        for(register int i = 1; i <= N; i++){

                cin >> temp;

                input.insert(pair<string, int>(temp, i));
                name[i] = temp;

        }

        for(register int i = 0; i < M; i++){

                cin >> temp;

                if(temp[0] >= '1' && temp[0] <= '9'){

                        int num = stoi(temp);

                        cout << name[num] << '\n';

                }

                else{
                        cout << input.find(temp)->second << '\n';
                }

        }

        return 0;

}

 

 

Hash 개념 정리

https://go-jowick.tistory.com/14

Hash c++ 개념 정리

Hash도 마찬가지로 하나의 Hash 테이블과 하나의 string 배열을 만들어 각각 저장 시켜주어 출력시키면 된다.

 

전체 코드

#include <bits/stdc++.h>

#define MAX_TABLE 100001

using namespace std;

struct Node{

        string str;
        int num;
        Node *next;

};

Node node_head[MAX_TABLE];
Node node[MAX_TABLE];
int node_cnt;

string num_list[MAX_TABLE];

int hashing(string input){

        int div = 401;

        int i = 0;
        int len = input.length();

        while(i != len){
                div = ((div << 5) + (int)input[i]) % MAX_TABLE;
                i++;
        }

        return div % MAX_TABLE;

}

void insert_str(string input, int num){

        int key = hashing(input);

        Node *temp = &node_head[key];
        Node *target = &node[node_cnt++];

        target->str = input;
        target->num = num;

        if(temp->next == 0){
                temp->next = target;
        }
        else{
                while(temp->next != 0){
                        temp = temp->next;
                }
                temp->next = target;
        }

        return;

}

int search_str(string input){

        int key = hashing(input);

        Node *temp = &node_head[key];

        while(temp->next != 0){
                if(temp->next->str == input){
                        break;
                }
                temp = temp->next;
        }

        return temp->next->num;

}

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int N, M;

        cin >> N >> M;

        string temp;

        for(register int i = 1; i <= N; i++){
                cin >> temp;
                num_list[i] = temp;
                insert_str(temp, i);
        }

        for(register int i = 0; i < M; i++){
                cin >> temp;
                if(temp[0] >= '1' && temp[0] <= '9'){
                        int num_temp = stoi(temp);
                    
                        cout << num_list[num_temp] << '\n';
                }
                else{
                        cout << search_str(temp) << '\n';
                }
        }

        return 0;

}