잼코딩 - 용만쌤

C++ - 1. set, map, unordered_set, unordered_map

12 min read

C++ - set, map, unordered_map, unordered_set

목표

C++ STL에서 자주 쓰는 연관 컨테이너를 연습합니다.

  • set: 중복 없는 값 저장, 자동 정렬
  • map: key-value 저장, key 기준 자동 정렬
  • unordered_set: 중복 없는 값 저장, 해시 기반
  • unordered_map: key-value 저장, 해시 기반

1. set

간략 설명

set은 중복을 허용하지 않고, 원소를 자동으로 정렬해서 저장하는 자료구조입니다.

  • 중복 저장 불가
  • 기본 오름차순 정렬
  • 삽입, 삭제, 탐색: O(log N)
  • 내부적으로 균형 이진 탐색 트리 기반

기본 사용법

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    set<int> s;
 
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(2); // 중복이므로 저장되지 않음
 
    for (int x : s) {
        cout << x << ' ';
    }
    // 출력: 1 2 3
 
    cout << "\n";
 
    if (s.find(2) != s.end()) {
        cout << "2가 존재합니다.\n";
    }
 
    s.erase(2);
 
    cout << s.count(2) << "\n"; // 0
}

자주 쓰는 함수

함수설명
insert(x)원소 x 삽입
erase(x)원소 x 삭제
find(x)원소 x의 iterator 반환
count(x)원소 존재 여부 반환. set에서는 0 또는 1
size()원소 개수
empty()비어 있는지 확인
begin()가장 작은 원소 위치
rbegin()가장 큰 원소 위치

주의: set은 []로 조회할 수 없다

set은 key-value 구조가 아니라 값 자체를 저장하는 자료구조입니다. 그래서 map처럼 s[key] 형태로 접근할 수 없습니다.

set<int> s;
 
s.insert(10);
 
// cout << s[10]; // 컴파일 에러

값이 있는지 확인할 때는 count()나 find()를 사용합니다. 이 방식은 원소가 없어도 새로 만들지 않습니다.

set<int> s;
 
if (s.count(10)) {
    cout << "10이 존재합니다.\n";
}
 
if (s.find(20) == s.end()) {
    cout << "20은 없습니다.\n";
}
 
cout << s.size() << "\n"; // 0

예시: 중복 제거 후 정렬 출력

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    int arr[] = {5, 3, 1, 3, 2, 5, 4};
    set<int> s;
 
    for (int x : arr) {
        s.insert(x);
    }
 
    for (int x : s) {
        cout << x << ' ';
    }
    // 출력: 1 2 3 4 5
}

2. map

간략 설명

map은 key와 value를 한 쌍으로 저장하는 자료구조입니다. key는 중복될 수 없고, key 기준으로 자동 정렬됩니다.

  • set에서 value가 추가된 형태라 이해
  • key 중복 불가
  • key 기준 오름차순 정렬
  • 삽입, 삭제, 탐색: O(log N)
  • 내부적으로 균형 이진 탐색 트리 기반

기본 사용법

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main() {
    map<string, int> score;
 
    score["kim"] = 90;
    score["lee"] = 85;
    score["park"] = 95;
 
    cout << score["kim"] << "\n"; // 90
 
    score["kim"] = 100; // 기존 value 수정
 
    for (auto [name, point] : score) {
        cout << name << ": " << point << "\n";
    }
}

자주 쓰는 함수

함수설명
m[key]key에 해당하는 value 접근. key가 없으면 새로 생성
insert({key, value})key-value 삽입
erase(key)key에 해당하는 원소 삭제
find(key)key에 해당하는 iterator 반환
count(key)key 존재 여부 반환. map에서는 0 또는 1
size()원소 개수
empty()비어 있는지 확인

주의: m[key]는 key가 없으면 새 원소를 만든다

map에서 m[key]를 사용하면 key에 해당하는 value에 접근합니다. 그런데 key가 없으면 value의 기본값을 넣어서 새 원소를 만듭니다.

map<string, int> m;
 
cout << m["apple"] << "\n"; // 0
 
// "apple"이라는 key가 없었지만,
// m["apple"]을 호출하는 순간 value 0으로 생성됨

조건문에서 확인만 하려는 경우에도 똑같이 새 원소가 생깁니다.

map<string, int> m;
 
if (m["apple"] == 0) {
    cout << "apple의 값은 0입니다.\n";
}
 
cout << m.count("apple") << "\n"; // 1
cout << m.size() << "\n";         // 1

자료형별 기본값 예시는 다음과 같습니다.

map<string, int> a;
map<string, string> b;
map<string, bool> c;
map<string, vector<int>> d;
 
cout << a["x"] << "\n"; // 0
cout << b["x"] << "\n"; // 빈 문자열
cout << c["x"] << "\n"; // false
cout << d["x"].size() << "\n"; // 0

key 존재 여부만 확인하고 싶을 때는 find() 또는 count()를 사용하는 것이 안전합니다. 이 방식은 없는 key를 새로 만들지 않습니다.

if (m.find("apple") != m.end()) {
    cout << "존재함\n";
}
 
if (m.count("apple")) {
    cout << "존재함\n";
}

key가 있을 때만 value를 비교하고 싶다면 iterator를 사용합니다.

auto it = m.find("apple");
 
if (it != m.end() && it->second == 3) {
    cout << "apple의 값은 3입니다.\n";
}

예시: 단어 개수 세기

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main() {
    string words[] = {"apple", "banana", "apple", "orange", "banana", "apple"};
    map<string, int> cnt;
 
    for (string word : words) {
        cnt[word]++;
    }
 
    for (auto [word, count] : cnt) {
        cout << word << ": " << count << "\n";
    }
}

3. unordered_set

간략 설명

unordered_set은 중복을 허용하지 않는 자료구조입니다. set과 달리 정렬되지 않고, 해시를 이용해 빠르게 탐색합니다.

  • 중복 저장 불가
  • 정렬 보장 없음
  • 평균 삽입, 삭제, 탐색: O(1)
  • 최악의 경우: O(N)
  • 내부적으로 해시 테이블 기반

기본 사용법

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main() {
    unordered_set<int> us;
 
    us.insert(10);
    us.insert(20);
    us.insert(10); // 중복 저장 안 됨
 
    if (us.count(20)) {
        cout << "20이 존재합니다.\n";
    }
 
    us.erase(10);
 
    for (int x : us) {
        cout << x << ' ';
    }
    // 출력 순서는 보장되지 않음
}

자주 쓰는 함수

함수설명
insert(x)원소 x 삽입
erase(x)원소 x 삭제
find(x)원소 x의 iterator 반환
count(x)원소 존재 여부 반환
size()원소 개수
empty()비어 있는지 확인

예시: 방문 여부 체크

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main() {
    unordered_set<int> visited;
 
    int path[] = {1, 3, 5, 3, 7};
 
    for (int node : path) {
        if (visited.count(node)) {
            cout << node << "는 이미 방문했습니다.\n";
        } else {
            visited.insert(node);
            cout << node << " 방문 처리\n";
        }
    }
}

4. unordered_map

간략 설명

unordered_map은 key-value를 저장하는 자료구조입니다. map과 달리 key 정렬을 보장하지 않고, 해시를 이용해 평균적으로 빠르게 탐색합니다.

  • key 중복 불가
  • key 정렬 보장 없음
  • 평균 삽입, 삭제, 탐색: O(1)
  • 최악의 경우: O(N)
  • 내부적으로 해시 테이블 기반

기본 사용법

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
 
int main() {
    unordered_map<string, int> age;
 
    age["kim"] = 20;
    age["lee"] = 25;
    age["park"] = 30;
 
    cout << age["lee"] << "\n"; // 25
 
    age["kim"]++;
 
    for (auto [name, value] : age) {
        cout << name << ": " << value << "\n";
    }
    // 출력 순서는 보장되지 않음
}

자주 쓰는 함수

함수설명
um[key]key에 해당하는 value 접근. key가 없으면 새로 생성
insert({key, value})key-value 삽입
erase(key)key에 해당하는 원소 삭제
find(key)key에 해당하는 iterator 반환
count(key)key 존재 여부 반환
size()원소 개수
empty()비어 있는지 확인

주의: unordered_map도 [] 접근 시 새 원소를 만든다

unordered_map도 map처럼 um[key]로 없는 key에 접근하면 value의 기본값으로 새 원소가 생성됩니다.

unordered_map<string, int> um;
 
if (um["apple"] == 0) {
    cout << "apple의 값은 0입니다.\n";
}
 
cout << um.count("apple") << "\n"; // 1

존재 여부만 확인할 때는 count() 또는 find()를 사용합니다.

예시: 숫자 등장 횟수 세기

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main() {
    int arr[] = {4, 1, 2, 4, 2, 4, 7};
    unordered_map<int, int> cnt;
 
    for (int x : arr) {
        cnt[x]++;
    }
 
    cout << "4의 개수: " << cnt[4] << "\n"; // 3
    cout << "2의 개수: " << cnt[2] << "\n"; // 2
}

set vs unordered_set

구분setunordered_set
중복불가능불가능
정렬자동 정렬정렬 안 됨
탐색O(log N)평균 O(1)
내부 구조트리해시 테이블
사용 기준정렬된 순서가 필요할 때빠른 존재 확인이 필요할 때

map vs unordered_map

구분mapunordered_map
key 중복불가능불가능
정렬key 기준 자동 정렬정렬 안 됨
탐색O(log N)평균 O(1)
내부 구조트리해시 테이블
사용 기준key 순서가 필요할 때빠른 key 검색이 필요할 때

연습 문제

1. 중복 제거하기

정수 N개가 주어졌을 때, 중복을 제거하고 오름차순으로 출력하세요.

  • 추천 자료구조: set<int>
입력 예시
7
5 3 1 3 2 5 4
 
출력 예시
1 2 3 4 5

2. 단어 개수 세기

문자열 N개가 주어졌을 때, 각 단어가 몇 번 등장했는지 출력하세요.

  • 추천 자료구조: map<string, int> 또는 unordered_map<string, int>
입력 예시
6
apple banana apple orange banana apple
 
출력 예시
apple 3
banana 2
orange 1

3. 출석 체크

학생 이름 목록이 주어지고, 특정 학생이 출석했는지 빠르게 확인하세요.

  • 추천 자료구조: unordered_set<string>
입력 예시
4
kim lee park choi
3
kim
han
park
 
출력 예시
YES
NO
YES

4. 번호로 이름 찾기

학생 번호와 이름이 주어졌을 때, 번호를 입력받아 이름을 출력하세요.

  • 추천 자료구조: unordered_map<int, string>
입력 예시
3
101 kim
102 lee
103 park
2
101
103
 
출력 예시
kim
park

빠른 선택 기준

  • 값의 중복 제거와 정렬이 필요하다면 set
  • key-value를 정렬된 key 순서로 다루고 싶다면 map
  • 값의 존재 여부를 빠르게 확인하고 싶다면 unordered_set
  • key-value를 빠르게 검색하고 싶다면 unordered_map

정렬된 결과가 필요 없고 빠른 탐색이 중요하다면 보통 unordered_set, unordered_map을 먼저 고려합니다.

Backlinks

  • No backlinks found

Mind Map

Graph View