std::map , std::unordered_map

 

이번에는 c++ 표준 라이브러리인 std::map, std::unordered_map 에 대해 알아보겠습니다.

 

라이브러리의 이름이 map 이라고 지어진 이유는 mapping 과 관련이 있기 때문입니다.

 

 

std::map (Ordered Map)

---

map 은 BST (이진탐색트리) , RedBlackTree(레드블랙트리) 로 구현되어 있어서

키의 순서가 자동으로 정렬되고

O(log N) 을 기대할 수 있습니다.

 

또, 트리의 형태를 유지하기 위해 추가적인 메모리를 사용하지만 Unordered_mapd 에 비하면 적고,

중복된 값은 허용하지 않습니다. ( 덮어쓰기 )

 

std::unordered_map (Unordered Map)

---

unordered_map 은 해시테이블로 구현되어 있어서

키의 순서가 정렬되지 않고

평균적으로 O(1) 을 기대할 수 있습니다. (최악의 경우 O(n) 이 될 수도 있음)

 

해시 테이블을 구성해야하기 때문에 더 많은 메모리를 사용해야 하고

중복된 키는 허용하지 않습니다.

 

 

라이브러리는 아래와 같이 불러오면 되고,

#include <map>
#include <unordered_map>

 

 

선언은 아래와 같이 해주면 됩니다.

std::unordered_map<type, type> m;
std::map<type, type> m1;

 

 

이제 실제로 어떻게 사용하는지 예제를 통해 살펴보겠습니다.

 

 

입력받은 로마숫자를 아라비아 숫자로 바꾸는 문제

---

https://leetcode.com/problems/roman-to-integer/description/

 

로마 숫자는 익숙치 않으실 수 있습니다.

아래 사진을 참고해주시길 바랍니다.

 

 

특징으로 알아둬야 할 것이 있습니다.

 

- 같은 문자가 두 번 쓰이면 *2 의 의미입니다.

 

- 작은 수 다음에 큰 수가 오는 경우, 큰 수에서 작은 수를 뺸 값이 결과입니다.

 

 

코드

#include <iostream>
#include <string>
#include <unordered_map>

class Solution {
 public:
  int romanToInt(std::string s) {
    std::unordered_map<char, int> m;
    m['I'] = 1;
    m['V'] = 5;
    m['X'] = 10;
    m['L'] = 50;
    m['C'] = 100;
    m['D'] = 500;
    m['M'] = 1000;

    int ans = 0;
    for (int i = 0; i < s.length(); i++) {
      auto val = m.find(s[i]);

      if (i + 1 < s.length() && val != m.end() && m.find(s[i + 1]) != m.end() &&
          m.find(s[i + 1])->second > val->second) {
        ans += (m.find(s[i + 1])->second - val->second);
        i++;
      } else
        ans += val->second;
    }

    return ans;
  }
};

int main(void) {
  Solution s;
  std::string str;

  std::cin >> str;
  std::cout << s.romanToInt(str) << '\n';

  return 0;
}

 

 

 

생일 역설의 확률을 구하는 예제

---

https://ko.wikipedia.org/wiki/%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C

생일 문제 - 위키백과, 우리 모두의 백과사전

n명의 사람이 모였을 떄 생일이 같은 사람이 있을 확률은 얼마일까? 라는 문제입니다.

 

이번 예제에서는 무작위로 생일을 입력받아 unordered_map을 이용해 테이블에 집어넣고 

중복되는 값이 있는지 없는지 판단하고 있습니다.

 

무작위 값으로 주어지기에 확률은 매번 조금씩 다르지만, 23명의 경우 50를 크게 벗어나지 않는 것을 

 

실행해보면 확인하실 수 있습니다.

 

#include <iostream>
#include <list>
#include <random>
#include <unordered_map>

template <typename T_KEY, typename T_VALUE>

void Print(const std::unordered_map<T_KEY, T_VALUE>& map) {
  for (int i = 0; i < map.bucket_count(); i++) {
    auto b = map.bucket(i);
    std::cout << i << ": ";
    for (auto j = map.begin(b); j != map.end(b); j++) {
      std::cout << "(" << j->first << ", " << j->second << ")->";
    }
    std::cout << '\n';
  }
}

int main(void) {
  std::random_device rd;
  std::mt19937 g(rd());
  std::uniform_int_distribution<int> dist(1, 365);

  int num_people = 23;

  std::unordered_map<int, int> map(num_people);

  int num_try = 1000;
  int all_samebirthday_count = 0;

  for (int t = 0; t < num_try; t++) {
    int samebirthday_count = 0;

    for (int i = 0; i < num_people; i++) {
      int birthday = dist(g);

      auto n = map.find(birthday);

      if (n != map.end()) {
        samebirthday_count += 1;
        n->second += 1;
      } else {
        map.insert({birthday, 1});
      }
    }

    if (samebirthday_count > 0) all_samebirthday_count += 1;

    map.clear();
  }
  std::cout << (all_samebirthday_count * 100 / num_try) << "%" << '\n';

  return 0;
}