13915 - 현수의 열기구 교실

현수는 열기구 여름특강의 강사다. 현수는 매우 성실해서 모든 수강생들의 열기구 비행을 기록하고있다. 매 비행 이후, 현수는 그 비행에 참석한 수강생들의 기록을 리스트에 추가한다. 리스트에는 각 수강생마다 띄웠던 기구의 인식번호만이 기록된다.

매 시즌이 끝난 후, 현수는 얼마나 많은 종류의 열기구들을 비행해봤는지에 따른 수강생들의 숙련도를 분류해 나열하려고한다. 만약 두 수강생이 비행했던 열기구의 종류들이 같다면 두 수강생은 같은 숙련도를 가진것으로 분류된다. (이 경우, 비행을 한 횟수는 관계가 없다.)

현수는 총 9 종류의 열기구를 관리하며, 수강생들의 기록은 각 열기구의 번호들로써 이루어진다. 모든 수강생들 중 비행 횟수가 9번을 넘는 수강생은 없다. (1번 열기구를 세번 2번과 3번을 각각 한번씩 운용했던 수강생의 번호는 11123이 되겠다.)

예를 들어, 수강생 234423과 수강생 342는 같은 숙련도를 가진 것으로 분류된다. 하지만 수강생 118821과 수강생 1189821 같은 경우는 9번 열기구 비행 유무의 차이로 다른 숙련도를 가진 것으로 분류된다.

현수의 리스트에 있는 수강생들이 총 몇개의 숙련도로 분류되는지 구하라.

C++ Solution 1

1#include <bits/stdc++.h> 
2using namespace std;
3
4int main() {
5    int t;
6  while(scanf("%d", &t) != EOF) {
7    unordered_map<string, int> m;
8    while(t--) {
9      string s; cin >> s;
10      sort(s.begin(), s.end());
11      string ns = "";
12      ns += s[0];
13      for(size_t i=1; i<s.size(); ++i) {
14        if(ns[ns.size()-1] != s[i]) ns += s[i];
15      }
16      m[ns] += 1;
17    }
18
19    auto it = m.begin();
20    int cnt = 0;
21    while(it != m.end()) {
22      ++cnt; ++it;
23    }
24
25    cout << cnt << endl;
26  }
27  return 0;
28}

C++ Solution 2

1#include <bits/stdc++.h> 
2using namespace std;
3
4int h(int k) {
5  int b = 0;
6  while(k) {
7    b |= (1 << (k%10));
8    k /= 10;
9  }
10  return b;
11}
12
13int main() {
14  int t;
15  while(scanf("%d", &t) != EOF) {
16    set<int> hashtable;
17    while(t--) {
18      int key; cin >> key;
19      hashtable.insert(h(key));
20    }
21    cout << hashtable.size() << endl;
22  }
23  return 0;
24}