백준(baekjoon) [C] - 1620번: 나는야 포켓몬 마스터 이다솜

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

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

---

#include <stdio.h>  // 나는야 포켓몬 마스터 이다솜
#include <stdlib.h>
#include <string.h>

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

int compare(void* first, void* second)
{
	node* a = (node*)first;
	node* b = (node*)second;
	if (strcmp(a->name, b->name) > 0)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

void binary_search(node* sorted, char* str, int n)
{
	int left, right, mid;

	left = 0, right = n - 1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (strcmp(sorted[mid].name, str) == 0)
		{
			printf("%d\n", sorted[mid].num);
			break;
		}
		else if (strcmp(sorted[mid].name, str) > 0)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
}


int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	node* list = (node*)malloc(sizeof(node) * n);
	node* sorted = (node*)malloc(sizeof(node) * n);

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

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

	char str[21];
	for (int i = 0; i < m; i++)
	{
		scanf("%s", str);
		if (str[0] >= '0' && str[0] <= '9')
		{
			int idx = atoi(str);
			printf("%s\n", list[idx - 1].name);
		}
		else
		{
			binary_search(sorted, str, n);
		}
	}

	free(list);
	free(sorted);

	return 0;
}

---

MEMO

-- 2차원배열을 생성해서 문자열을 입력받고 탐색 x

-- 처음에는 위의 방법처럼 하려다가 공간이 너무 커져서 불가

-- 구조체에 name과 num(인덱스)를 저장

-- 오름차순 정렬 후 이진탐색 사용

 

!! 구조체 활용 잘하기 !!