BOJ
백준 [C 언어] 1620 : 나는야 포켓몬 마스터 이다솜
횰임
2022. 3. 3. 13:57
✅ 문제
요약)
1. N개의 포켓몬 (1번~N번) 이름 주어짐 (포켓몬 도감)
2. M개의 문제 주어짐 (포켓몬 번호나 이름)
3. 문제에 대한 답 출력 (포켓몬 번호나 이름 매칭시키기)
✅ 해결 과정
1. 포켓몬 번호와 이름을 1:1 매칭--> 해시 테이블 사용
2. 포켓몬 번호를 key, 이름을 value로 저장하고 key를 해시 index로 변환해 해시 테이블에 add (연결리스트 사용)
3. 문제 입력 받고 문제가 번호면 이름을, 이름이면 번호를 출력
✅ 구조체 선언부
1. 노드 구조체
//노드 구조체
typedef struct __node
{
int key; //포켓몬 번호
char value[MAX_NAME]; //포켓몬 이름
struct __node *next; //다음 노드 포인터
} Node;
2. 버킷 구조체
//버킷 관리
typedef struct __bucket
{
Node *head; //한 버켓의 첫 번째 노드
int count; //한 버켓의 노드 개수
} Bucket;
✅ 주요 함수
1. createNode : 새 노드 생성
//노드 생성하기
Node* createNode(int key, char value[])
{
Node *newNode = calloc(1, sizeof(Node));
newNode->key = key;
strcpy(newNode->value, value);
newNode->next = NULL;
return newNode;
}
2. hashFunction : 해시 함수 (key를 Hash index로 변환해줌)
//해시 함수
int hashFunction(int key)
{
return key % BUCKET_SIZE;
}3. add : key와 value를 해시 테이블에 추가
//노드 추가
void add(int key, char value[])
{
//Hash index 계산
int hashIndex = hashFunction(key);
//새 노드 생성
Node *newNode = createNode(key, value);
//빈 버킷인 경우 head를 newNode로
if(hashTable[hashIndex].count == 0)
{
hashTable[hashIndex].count++;
hashTable[hashIndex].head = newNode;
}
else
{
newNode->next = hashTable[hashIndex].head;
hashTable[hashIndex].head = newNode;
hashTable[hashIndex].count++;
}
return;
}
4. search_key : key가 갖고 있는 value를 찾아줌
//key에 대응하는 value 출력
void search_key(int key)
{
//hash index 계산
int hashIndex = hashFunction(key);
//iterator 노드를 머리 노드로 초기 설정
Node *node = hashTable[hashIndex].head;
//검색 성공하면 flag==1
int flag = 0;
while(node != NULL)
{
if(node->key == key) //키 일치
{
flag = 1;
break;
}
node = node->next;
}
if(flag == 1)
{
printf("%s\n", node->value); //이름 출력
}
return;
}
5. search_value : value에 해당하는 key를 찾아줌
//문자열 검색
void search_value(char value[])
{
Node *node;
int flag = 0;
for(int i=1; i<BUCKET_SIZE; i++)
{
node = hashTable[i].head;
while(node != NULL)
{
if(strcmp(node->value, value) == 0) //이름 일치
{
flag = 1;
break;
}
node = node->next;
}
if(flag == 1)
{
printf("%d\n", node->key); //키 출력
}
}
}
6. main 함수
int main(void) {
int N, M;
char pocket_name[21];
char quiz[21];
int i = 0;
scanf("%d %d", &N, &M);
//도감 입력받기
while(N != 0)
{
scanf("%s", pocket_name);
add(i+1, pocket_name); //key:1번~N번, value: 이름
N--;
}
while(M != 0)
{
//문제 입력받기
scanf("%s", quiz);
int flag = atoi(quiz); //알파벳: 0반환, 숫자: 정수 반환
//이름이 문제일 때
if(flag == 0)
{
search_value(quiz);
}
else{
search_key(flag);
}
M--;
}
return 0;
}
👊 Try 1
➡️ 메모리 해제, 포인터 잘못 쓴거 있나 확인했는데 오류 해결 못함, 복잡
👊 Try 2
- HashTable 사용 X : 버킷 구조체와 해시 관련 함수들 지움
- 노드를 요소로 하는 크기 N 리스트 1개 생성하고 포켓몬 도감 입력받기
- 문제가 포켓몬 번호라면 atoi( ) 사용해 정수로 변환하고 바로 리스트에 접근해서 이름 출력
- 문제가 포켓몬 이름이라면 리스트 이진탐색해서 번호 찾기 --> 그 전에 퀵소트 사용한 정렬 필요
✅ 주요 코드
1. 도감 테이블, 정렬된 테이블 생성 & 포켓몬 입력받기
pocket_list = (Node*)malloc(n * sizeof(Node)); //포켓몬 도감 테이블 생성
sorted_list = (Node*)malloc(n * sizeof(Node)); //알파벳 순 정렬된 도감 테이블 생성 (이진탐색 위함)
//포켓몬 입력받기
for(i = 0; i < n; i++)
{
scanf(" %s", pocket_list[i].name);
pocket_list[i].no = i + 1;
sorted_list[i] = pocket_list[i]; //테이블 복사
}
qsort(sorted_list, n, sizeof(sorted_list[0]), compare); //도감 알파벳순 정렬
2. 문제 입력받기 & 답 출력하기
//문제 입력받기
for(i = 0; i < m; i++)
{
scanf(" %s", quiz);
//숫자(1~9)라면
if(quiz[0] >= '1' && quiz[0] <= '9')
{
int idx = atoi(quiz); //포켓몬 번호 정수화
printf("%s\n", pocket_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, quiz) == 0) //검색 성공
{
printf("%d\n", sorted_list[mid].no); //번호 출력
break;
}
else if(strcmp(sorted_list[mid].name, quiz) > 0)
right = mid - 1;
else
left = mid + 1;
}
}
}
✅ 전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME 21
//노드
typedef struct __node
{
int no;
char name[MAX_NAME];
} Node;
//qsort위한 비교힘수
int compare(const void* first, const void* second)
{
Node *a = (Node*)first;
Node *b = (Node*)second;
if(strcmp(a->name, b->name) > 0)
return 1;
else
return -1;
}
int main()
{
int n, m, i;
Node* pocket_list = NULL;
Node* sorted_list = NULL;
char quiz[MAX_NAME];
scanf("%d %d", &n, &m);
//포켓몬 도감 테이블 생성
pocket_list = (Node*)malloc(n * sizeof(Node));
//알파벳 순 정렬된 도감 테이블 생성 (이진탐색 위함)
sorted_list = (Node*)malloc(n * sizeof(Node));
for(i = 0; i < n; i++)
{
scanf(" %s", pocket_list[i].name);
pocket_list[i].no = i + 1;
sorted_list[i] = pocket_list[i]; //테이블 복사
}
qsort(sorted_list, n, sizeof(sorted_list[0]), compare);
//도감 알파벳순 정렬
//문제 입력받기
for(i = 0; i < m; i++)
{
scanf(" %s", quiz);
if(quiz[0] >= '1' && quiz[0] <= '9') //숫자라면 (1~9)
{
int idx = atoi(quiz); //포켓몬 번호
printf("%s\n", pocket_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, quiz) == 0) //검색 성공
{
printf("%d\n", sorted_list[mid].no); //번호 출력
break;
}
else if(strcmp(sorted_list[mid].name, quiz) > 0)
right = mid - 1;
else
left = mid + 1;
}
}
}
free(sorted_list);
free(pocket_list);
return 0;
}