[13414번] 수강신청

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 해쉬(Hash) 이용

이 문제는 여러가지 방법이 있으나 필자는 해쉬로 풀어보았다.

해쉬 함수를 이용하면 좋은점은 O(1)에 모든것이 해결이 가능하다는 것이다.

이 문제는 1차원 단일 해쉬로 해결하였고, 메모리가 조금 많이 든다는 단점은 있다.

배열 범위를 11000000으로 둔 이유는

학생번호가 8자리이고, 최대 50만개가 올 수 있으니

99,999,999가 50만개가 오면 100,499,999가되니, 최대 배열은 100,500,000개가 필요하다.

그리고 해쉬 크기는 적당한 수 200만으로 잡고 진행하였다.

자세한 내용은 주석을 통해 달아두었다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

#include <cstring> #include <iostream> #include <algorithm>   using namespace std;   typedef struct _student {     int num;     int order;   }Student;     bool comp(Student const& a, Student const& b) {       return a.order > b.order; }   Student stu[11000000]; int order = 1; int cnt = 0;   int main() {     int n, m, t = 0;     int val;       scanf("%d%d", &n, &m);         for (int i = 0; i < 11000000; i++)     {         stu[i].num = -1;     }       for (int i = 0; i < m; i++)     {         scanf("%d", &val);           // 해쉬에 이미 값이 있다면         if (stu[val % 2000000].num != -1)         {             // 그 해쉬에 값이 현재 넣으려는 값과 같다면 순번만 바꾼다             if (stu[val % 2000000].num == val)                 stu[val % 2000000].order = order;               // 해쉬 테이블의 빈자리를 찾을 때 까지 돌린다.             else             {                 for (int j = 0; ; j++)                 {                     // 찾는 도중 그 자리에 값이 같은 값이라면                     if (stu[val % 2000000 + j].num == val)                     {                         stu[val % 2000000 + j].order = order;                         break;                     }                     // 빈자리를 찾았다면                     if (stu[val % 2000000 + j].num == -1)                     {                         stu[val % 2000000 + j].num = val;                         stu[val % 2000000 + j].order = order;                         break;                     }                 }             }         }         // 값이 없다면 바로 넣는다.         else         {             stu[val % 2000000].num = val;             stu[val % 2000000].order = order;         }           order++;     }       sort(stu, stu + 10500000, comp);       // 오름차순 정렬된 값 중 -1이 나올 때 까지, 즉, 마지막 값 찾기과정     for (t = 0; stu[t].num != -1; t++){}       cnt = t;     // ex 5 4 3 2 1로 정렬되어있고 3개만 찾으면 되면 1 2 3을 출력     for (int i = 0; i < n && i < cnt; i++)     {         printf("%.8d\n", stu[t - 1].num);         t--;     } }     //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus