[C] 백준 | 1620번 코드 - 나는야 포켓몬 마스터 이다솜!

>문제

너무 길다

생략!

www.acmicpc.net/problem/1620

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

> 핵심

탐색 알고리즘

(이분탐색)

>풀이과정

맨 처음에 그냥 문자열 배열으로 주욱 입력받은 다음에 이중반복문으로 뺑뺑이 돌리려고 했는데 시간초과가 나서 방법을 수정해야 했다..

 

O(n^2)보다 빠른 탐색 방법이라면 이분탐색(O(logn))이 쉽고 대표적이기에 이분탐색을 사용했다.

 

이분탐색을 사용하려면 우선 배열이 정렬되어있어야 하므로 list외에 추가로 sorted_list를 할당하고 qsort를 이용해 정렬.

 

>깨달은점

포켓몬 마스터 이다솜 화이팅

>코드

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

typedef struct
{
    int num;
    char name[21];
}monster;

int compare(const void* first, const void* second)
{
    monster *a = (monster*)first;
    monster *b = (monster*)second;

    if (strcmp(a->name, b->name) > 0)
        return 1;
    else
        return -1;
}

int main()
{
    int n, m, i;
    monster* list = NULL;
    monster* sorted_list = NULL;
    char op[21];

    scanf("%d %d", &n, &m);
    
    list = (monster*)malloc(n * sizeof(monster));
    // 정렬을 위해서..!
    sorted_list = (monster*)malloc(n * sizeof(monster));

    for (i = 0; i < n; i++)
    {
        scanf(" %s", list[i].name);
        list[i].num = sorted_list[i].num = i + 1;
        sorted_list[i] = list[i];
    }

    qsort(sorted_list, n, sizeof(sorted_list[0]), compare);

    for (i = 0; i < m; i++)
    {
        scanf(" %s", op);

        if (op[0] >= '0' && op[0] <= '9')
        {
            int idx = atoi(op);
            printf("%s\n", list[idx - 1].name);
        }
        // 이진탐색
        else
        {
            int left, right, mid;
            left = 0, right = n - 1;

            while (left <= right)
            {
                mid = (left + right) / 2;

                if (strcmp(sorted_list[mid].name, op) == 0)
                {
                    printf("%d\n", sorted_list[mid].num);
                    break;
                }
                else if (strcmp(sorted_list[mid].name, op) > 0)
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
        }
    }
    
    free(sorted_list);
    free(list);

    return 0;
}