1620번 나는야 포켓몬 마스터 이다솜 - 해시

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct _poke {
    int n[50000];  //포켓몬 번호
    int num;  //개수
} poke[27][27];


int f(char a)  //소문자를 대문자로 바꿔줌
{
    return a>='a' ? a-20-'A':a-'A';
}

int main()
{
    int N, M;
    int i, j, k;
    char name[100000][21]={};
    char s[21];
    
    scanf("%d %d", &N, &M);
    
    for(i=1; i<=N; i++) {
        scanf("%s", name[i]);  //포켓몬 이름 받기
        
        poke[f(name[i][0])][f(name[i][1])].n[poke[f(name[i][0])][f(name[i][1])].num++]=i;
    }  //앞에 두 글자로 나누기
    
    for(i=0; i<M; i++) {
        scanf("%s", s);
        if(s[0]>='A') {  //문자열임
            for(j=0; j<poke[f(s[0])][f(s[1])].num; j++) {
                if(!strcmp(name[poke[f(s[0])][f(s[1])].n[j]], s)) {
                    printf("%d\n", poke[f(s[0])][f(s[1])].n[j]);
                    break;
                }
            }
        }
        else
            printf("%s\n", name[atoi(s)]);
    }
    
    return 0;
}

 

atoi(list): list 문자열을 정수로 반환하고, 숫자가 아닐 경우 0을 반환한다. <stdlib.h>

strcmp(s1, s2): 문자열 s1이 문자열 s2보다 크면 1, 작으면 0, 같으면 0을 반환한다. <string.h>

100000만번을 판단해야했기 때문에 strcmp로 일일이 판단하는 것은 무리라고 판단.

앞에 두 글자만 선택해서 이차원 배열에 나눠서 저장했다. 다 풀고 나서 다른 사람 코드를 보는데 해시로 푸는 사람도 있었다.

 

처음보는 알고리즘이라서 블로그에서 공부했다. 링크는 아래에

 

<strcmp()>

https://dojang.io/mod/page/view.php?id=346 

C 언어 코딩 도장: 41.2 문자열 비교하기

 

<atoi()>

https://dojang.io/mod/page/view.php?id=385 

C 언어 코딩 도장: 46.1 문자열을 정수로 변환하기

 

<구조체>

https://dojang.io/mod/page/view.php?id=408 

C 언어 코딩 도장: 48.1 구조체를 만들고 사용하기

 

<자료구조 - 해시>

https://go-coding.tistory.com/30

[자료구조] Hash의 개념 및 설명

 

내가 봤던 코드. 솔직히 보고 감탄했다. (한 번 풀어야 볼 수 있습니다.)

https://www.acmicpc.net/source/38626243

로그인

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.