[BOJ] 백준 14670 병약한 영정

출처: https://www.acmicpc.net/problem/14670 

 Input 

3

1 3

4 2

99 1

4

1 1

2 4 99

3 4 1 99

1 5

 

 Output 

3

2 1

2 3 1

YOU DIED

어떤 약의 이름, 효능과 중복되지 않음을 보장되므로

Hash Table에 약의 효능 = key, 약의 이름 = value로 두어서

증상에 대해 해결 가능한지 빠르게 확인할 수 있습니다.　

 

▶ [해시] Hash란?

[해시] Hash란?

STL

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
 
using namespace std;
map<int, int> item;
int pill[100];
int main(){
    // freopen("input.txt", "r", stdin);
    int N; scanf("%d", &N);
 
    int effect, ID;
    for (int i = 0; i < N; i++){
        scanf("%d %d", &effect, &ID);
        // Hash 구성
        item[effect] = ID;
    }
 
 
    int R;  scanf("%d", &R);
    int symptom, cnt;
    bool isOk;
    for (int i = 0; i < R; i++){
        scanf("%d", &cnt);
        isOk = true;
        for (int j = 0; j < cnt; ++j) {
            scanf("%d", &symptom);
            if (item.count(symptom) != 0)
                pill[j] = item[symptom];
            else
                isOk = false;
        }
 
        if (isOk) { // 모든 증상이 치료가능하다면
            for (int j = 0; j < cnt; ++j) {
                printf("%d ", pill[j]);
            }   
        }
        else {
            printf("YOU DIED");
        }
        printf("\n");
    }
}

 

Chaining 방식

- 테이블 크기를 약의 최대 개수로 잡아도 무방하지만 체이닝 방식을 위해서 53정도로 설정

#include <stdio.h>
 
const int SIZE = 53; // 소수
const int MOD = SIZE - 1;
const int MAX_N = 100;
struct Node {
       int effect, ID;
       Node* next;
       Node* alloc(int effect, int ID, Node *np) {
              this-> effect = effect, this->ID = ID, next = np;
              return this;
       }
}buf[MAX_N + 10], *htab[SIZE];
int bcnt, pill[MAX_N + 10];
 
Node* probing(int hidx, int symptom) {
       Node* p = htab[hidx];
       for (; p; p = p->next) {
              if (p->effect == symptom)
                     return p;
       }
       return NULL;
}
 
int main() {
       // freopen("input.txt", "r", stdin);
       int N; scanf("%d", &N);
       int effect, ID;
       for (int i = 0; i < N; ++i) {
              scanf("%d %d", &effect, &ID);
              int hidx = effect & MOD;
              htab[hidx] = buf[bcnt++].alloc(effect, ID, htab[hidx]);
       }
       int R; scanf("%d", &R);
       int cnt, symptom;
       bool isOk;
       for (int i = 0; i < R; ++i) {
              
              scanf("%d", &cnt);
              isOk = true;
              for (int j = 0; j < cnt; ++j) {
                     scanf("%d", &symptom);
                     int hidx = symptom & MOD;
                     // 해당 증상에 해당되는 약 확인
                     Node* p = probing(hidx, symptom);
                     if (p) {
                           pill[j] = p->ID;
                     }
                     else {
                           isOk = false;
                     }
              }
              
              if (isOk) {
                     for (int j = 0; j < cnt; ++j) {
                           printf("%d ", pill[j]);
                     }
              }
              else {
                     printf("YOU DIED");
              }
              printf("\n");
       }
}