자료구조 (맵)

맵(Map, Dictionary)

맵이란 Key와 Value가 한 쌍으로 구성되어 있는 자료 구조이다 여기서 Value는 중복이 가능하지만 Key는 중복이 불가능하다

맵은 C++과 Python에서 다르게 구현되어 있는데 C++은 Red-Black Tree로 구현되어 있으며 삽입/삭제 속도가 O(log N)이고 Python으로는 Hash로 구현되어 있으며 삽입/삭제 속도가 O(1)이다

C++ 코드로는 이렇게

map<string, int> m;

m["a"] = 0;
m["b"] = 1;
m["c"] = 2;
m["d"] = 3;

cout << "size: " << m.size();

for (auto p : m) {
    cout << p.first, p.second;
}

Python 코드로는 이렇게 구현할 수 있다

m = {}

m["a"] = 0
m["c"] = 1
m["b"] = 2
m["d"] = 3

print(f"size: {len(m)}")

for k in m:
    print(k, m[k])