[BOJ/C++] 단계별로 풀어보기 - 집합과 맵

2026.01.22일차입니다.
많이 늦었습니다. 좀 힘들었어서
아무튼 집합과 맵 풀어보았습니다.

10815번 숫자 카드

문제 링크
빠른 탐색을 필요로 하는 문제입니다. 이진 탐색(Binary search) 또는 map을 이용하여 풀 수 있습니다.

Binary search

이진 탐색(Binary search)이란 탐색 범위를 절반 씩 줄여 나가는 효율적인 탐색 알고리즘입니다.
선형 탐색에 비해 빠르지만 배열이 정렬되어 있어야 동작합니다.
시간 복잡도는 O(log n) 입니다.

이미지 출처

주어진 범위 내에서 찾는 값이 중간 값보다 크다면 중간 값 + 1 ~ 끝 범위 내에서 다시 탐색합니다.
찾는 값이 중간 값보다 작다면 처음 ~ 중간 값 - 1 범위 내에서 탐색합니다.
이를 계속 반복하며 탐색 범위를 줄여나갑니다.
중간 값과 찾는 값이 일치한다면 탐색에 성공한 것이고 처음 범위가 끝 범위보다 커졌다면 해당 배열 내에 찾는 값이 없다는 뜻이 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

bool binary_search(int a[], int s, int k) {
    int l = 0, h = s - 1;
    while (l <= h) {
        int m = (l + h) / 2; if (k == a[m]) return 1;
        if (k < a[m]) h = m - 1; else l = m + 1;
    } return 0;
}

int main() {
    int N, M; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a, a + N); cin >> M; int* r = new int[M]; for (int i = 0; i < M; ++i) cin >> r[i];
    for (int i = 0; i < M; ++i) cout << binary_search(a, N, r[i]) << ' ';
}

코드로 구현하면 다음과 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, M; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i]; 
    cin >> M; int* r = new int[M]; for (int i = 0; i < M; ++i) cin >> r[i];
    sort(a, a + N); for (int i = 0; i < M; ++i) cout << binary_search(a, a + N, r[i]) << ' ';
}

하지만 <algorithm> 태그에서 binary_search 함수로 지원하기 때문에 직접 구현할 필요는 없습니다.

map

map이란 <map> 헤더 내에 포함된 C++ STL 연관 컨테이너 중 하나입니다.
자가 균형 이진 탐색 트리라는 레드-블랙 트리를 자료구조를 사용하며 탐색, 삽입, 삭제 연산 시 균형을 유지하여 최악의 경우에도 O(log n)의 빠른 속도를 보장합니다.
map<key, value> 의 형태로 이루어져 있으며 map[key] = value 형태로 작성이 가능합니다.

코드는 다음과 같이 작성할 수 있습니다.

#include <iostream>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; map<int, int> m; cin >> N; for (int i = 0; i < N; ++i) { int t; cin >> t; m[t] = 1; }
    cin >> M; for (int i = 0; i < M; ++i) { int t; cin >> t; cout << m[t] << ' '; }
}

key와 value 모두 int형으로 선언합니다.
map에서 map[key]을 호출하였을 때 해당 key가 존재하지 않는다면 새로운 요소를 생성합니다.
만약 map[key] = value처럼 대입 연산자를 통하여 값을 대입하면 <key, value> 형태의 새로운 요소를 생성하지만 map[key]만을 작성한다면 value의 디폴트 값에는 0이 들어가 <key, 0>이 저장됩니다.
따라서 map을 사용한 해당 코드는 저장되지 않았어도 0을 출력할 수 있는 것입니다.
또한 해당 코드는 ios::sync_with_stdio(false); cin.tie(NULL);를 생략하면 시간 초과가 발생합니다.

Binary search vs map

두 방식 모두 시간 복잡도는 O(log n)으로 같습니다.
그런데 ios::sync_with_stdio(false); cin.tie(NULL);를 포함했을 때 Binary search 방식은 208ms, map은 444ms가 소요되었습니다.
배열과 벡터가 map보다 더 빠른 속도를 보여줍니다.
따라서 둘의 시간 복잡도가 같음에도 binary search가 더 빠른 속도를 보입니다.

14425번 문자열 집합

문제 링크
map을 사용하여 <요소, 등장 여부> 형태로 저장합니다. 등장한다면 1, 아니라면 0입니다. 해당 여부는 [key] 방식 또는 count 메소드를 통해 알 수 있습니다.

[key]

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, s = 0; map<string, int> mp; cin >> N >> M; while (N--) { string t; cin >> t; mp[t] = 1; }
    while (M--) { string t; cin >> t; s += mp[t]; } cout << s;
}

요소를 저장했다면 map[key]의 결과는 1, 아니라면 디폴트 값인 0이 저장됩니다.
9924 KB, 64 ms가 소요됩니다.

count

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, s = 0; map<string, int> mp; cin >> N >> M; while (N--) { string t; cin >> t; mp[t] = 1; }
    while (M--) { string t; cin >> t; s += mp.count(t); } cout << s;
}

count 메소드는 key 값의 개수를 반환합니다. (하지만 map에서는 key가 중복되지 않으므로 1 또는 0 밖에 반환하지 않습니다.)
[key] 방식과의 차이점이 있다면 [key] 방식은 해당 요소가 없다면 새로운 메모리를 할당하여 생성해야 하지만, count 방식은 0만을 반환하면 됩니다.
따라서 [key] 방식보다 사용 메모리가 낮고 빠른 7944 KB, 56 ms가 소요됩니다.

교집합?

다른 풀이가 있는지 고민하던 중 교집합을 사용하여 풀 수 있지 않을까 하는 생각을 해봤습니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, M; cin >> N >> M; vector<string> v1(N), v2(M), r;
    for (int i = 0; i < N; ++i) cin >> v1[i]; for (int i = 0; i < M; ++i) cin >> v2[i]; sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end());
    set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(r)); cout << r.size();
}

두 배열을 생성하여 N개의 문자열, M개의 검사할 문자열을 저장하였습니다.
교집합을 진행하기 위해 두 배열을 각각 오름차순 정렬 후 <algorithm> 헤더 내에 포함되어 있는 set_intersection 함수를 사용하여 두 배열의 교집합을 계산할 수 있습니다. 해당 함수의 형태는 위의 코드를 참고 바랍니다.
그런데 back_inserter라는 함수가 있습니다. back_inserter는 공간을 계산하지 않고 넣는 횟수만큼 push_back을 호출하는 함수입니다.

vector<int> v = {1, 2, 3}, res;
copy(v.begin(), v.end(), res.begin());

이러한 상황에서 res vector는 크기가 0으로 공간이 할당되지 않아 덮어쓸 메모리가 없어 오류가 발생합니다.
이 때 back_inserter를 사용하면 해당 배열에 자동으로 push_back을 호출하며 안전하게 요소를 대입할 수 있습니다.

하지만 결과적으로 오답이었습니다.

입력
첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.
다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.
다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.
입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

문제 설명이며 집합 S에는 중복이 없다고 주어져 있지만 검사할 문자열에 중복이 없다는 말은 없습니다.
따라서 검사할 문자열에 중복이 있을 경우 교집합 결과가 다르게 나올 수 있어 교집합을 사용한 코드는 오답입니다.

7785번 회사에 있는 사람

문제 링크
set을 이용한 문제입니다.
set은 <set> 헤더 내에 포함된 C++ STL 연관 컨테이너로 map과 같이 레드-블랙 트리로 이루어져 있습니다.
set은 중복을 허용하지 않으며, 삽입 순서에 상관없이 자동 정렬이 됩니다.
set<자료형> 변수 형태로 선언 가능합니다.

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
    int n; set<string> s; cin >> n;
    while (n --> 0) { 
        string t, b; cin >> t >> b;
        if (b == "enter") s.insert(t); else s.erase(t);
    } for (auto i = s.rbegin(); i != s.rend(); ++i) cout << *i << '\n';
}

"enter"가 입력되면 삽입, "leave"가 입력되면 삭제합니다.
set.erase(value)는 값을 토대로 삭제하기 때문에 set을 사용합니다.
또한 사전 순의 역순으로 출력해야 하기 때문에 자동 정렬되는 set을 역순으로 출력해야 합니다.

이미지 출처
rbegin과 rend를 사용하여 역순을 만들 수 있습니다.

--> 문법에 대한 내용은 다음 영상을 참고 바랍니다.

1620번 나는야 포켓몬 마스터 이다솜

문제 링크
숫자를 입력 받으면 번호에 대응하는 이름, 문자를 입력 받으면 이름에 대응하는 번호를 반환해야 합니다.
따라서 <이름, 번호>, <번호, 이름> 두 가지의 map을 만들어야 합니다.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; map<int, string> mp1; map<string, int> mp2; cin >> N >> M; for (int i = 1; i <= N; ++i) { cin >> mp1[i]; mp2[mp1[i]] = i; }
    while (M--) {
        string t; cin >> t; 
        try { cout << mp2.at(t) << '\n'; } catch (out_of_range) { cout << mp1.at(stoi(t)) << '\n'; }
    }
}

at 메소드에 Key를 넘기면 Value를 받을 수 있습니다. 그런데 해당 key가 존재하지 않으면 예외를 발생합니다. 해당 방법을 이용하여 문제를 풀어봅니다.
먼저 <이름, 번호> map에 at을 이용하여 접근하고 해당 부분을 try로 묶어줍니다.
해당 부분에서 예외가 발생하였다면 값이 존재하지 않는다는 뜻이고 이는 곧 숫자를 입력 받았으므로 <번호, 이름> map에서 접근해야 한다는 뜻입니다.
stoi 함수를 이용하여 입력 받은 string형을 int형으로 변환하고 <번호, 이름> map에서 접근하도록 합니다.
25528 KB, 360 ms가 소요되었습니다.

<번호, 이름> map의 경우에는 배열로 선언 가능하며 앞에서 설명했듯 배열이 map보다 빠른 속도를 보여줍니다.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M; string* a = new string[N + 1]; map<string, int> m;
    for (int i = 1; i <= N; ++i) { cin >> a[i]; m[a[i]] = i; }
    while (M--) {
        string t; cin >> t;
        if (isdigit(t[0])) cout << a[stoi(t)] << '\n'; else cout << m[t] << '\n';
    }
}

<배열, 이름> map을 배열로 선언한 코드이며 해당 코드는 입력값이 숫자인지 판단하는 방법으로 isdigit 함수를 사용하였습니다.
isdigit 함수는 char값이 숫자인지 문자인지를 판단하는 함수입니다.
첫 번째 요소가 숫자라면 해당 문자열은 숫자입니다.
20864 KB, 144 ms가 소요되며 두 개의 map을 사용한 코드보다 효율적입니다.

10816번 숫자 카드 2

문제 링크
숫자를 입력 받고 해당 숫자가 몇 번 등장하는지 세는 문제입니다.
map으로도 구현이 가능하며 배열로도 구현이 가능합니다.

map

#include <iostream>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N; map<int, int> m; cin >> N; while (N--) { int t; cin >> t; m[t] += 1; }
    cin >> N; while (N--) { int t; cin >> t; cout << m[t] << ' '; }
}

입력 받은 요소를 Key로 하여 입력 받을 때마다 값을 1씩 증가시킵니다.
이후 입력 받은 Key에 대응하는 Value를 출력하는 평범한 map 문제입니다.

배열

map을 사용하지 않고 어떻게 풀 수 있을지 고민을 많이 했습니다.
입력 받은 요소를 배열에 저장한 뒤 오름차순 정렬합니다.
이후 배열 내에서 그 요소가 등장한 마지막 위치 - 첫 위치가 그 요소의 등장 개수입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    cin >> M; sort(a, a + N); while (M--) { int t; cin >> t; cout << upper_bound(a, a + N, t) - lower_bound(a, a + N, t) << ' '; }
}

upper_bound는 해당 요소를 초과하는 숫자가 배열 어디에서 처음 등장하는 지를 반환합니다. 이는 정렬된 배열에서 해당 요소가 마지막으로 등장하는 위치 + 1과 같습니다.
lower_bound는 찾으려는 요소가 처음 등장하는 위치를 반환합니다.
따라서 upper_bound - lower_bound는 해당 요소의 개수가 됩니다.

1764번 듣보잡

문제 링크
교집합 문제이며 교집합, map, binary search 세 가지 방법을 사용하여 풀 수 있습니다.

교집합

14425번 문자열 집합에서 오답으로 사용했던 set_intersection을 사용하여 풀 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M; vector<string> v1(N), v2(M); 
    for (int i = 0; i < N; ++i) cin >> v1[i]; for (int i = 0; i < M; ++i) cin >> v2[i]; 
    sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end());
    vector<string> r; auto t = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(r));
    cout << r.size() << '\n'; for (string n : r) cout << n << '\n';
}

map

<이름, 등장 횟수> map을 생성하여 등장 횟수가 1보다 크면(즉, 2번) 두 집합에 모두 등장했다는 뜻이므로 교집합에 들어갑니다.
따라서 이러한 요소들을 결과 vector에 대입합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; map<string, int> m; vector<string> v; cin >> N >> M;
    for (int i = 0; i < N + M; ++i) {
        string t; cin >> t; m[t]++;
        if (m[t] > 1) v.push_back(t);
    } sort(v.begin(), v.end()); cout << v.size() << '\n'; for (string t : v) cout << t << '\n';
}

binary search

첫 번째 집합을 모두 배열에 저장합니다.
이후 두 번째 배열의 요소는 입력받으면 해당 요소가 첫 번째 배열에 존재하는지 binary search를 통해 확인합니다.
존재한다면 교집합에 포함되므로 결과 배열 내에 저장합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, M; cin >> N >> M; vector<string> v(N), r; for (int i = 0; i < N; ++i) cin >> v[i];
    sort(v.begin(), v.end()); while (M--) { string t; cin >> t; if (binary_search(v.begin(), v.end(), t)) r.push_back(t); }
    sort(r.begin(), r.end()); cout << r.size() << '\n'; for (string t : r) cout << t << '\n';
}

교집합 vs map vs binary search

세 코드의 성능 차이는 다음과 같습니다.

구분	교집합	map	binary search
메모리	9912 KB	12992 KB	5972 KB
시간	32 ms	72 ms	24 ms

map 특성상 map을 사용한 코드가 배열의 사용한 코드보다 느린 속도로 나타납니다.
또한 교집합 코드는 사용한 배열이 총 세 개, binary search 코드는 사용한 배열이 총 2개였기 때문에 binary search 코드가 더 적은 메모리를 사용했습니다.
해당 지표에서는 binary search 코드가 가장 효율적인 것으로 나타났습니다.

1269번 대칭 차집합

문제 링크
A-B와 B-A의 합집합을 대칭 차집합이라고 합니다. 합집합에서 교집합을 제외한 것과 같습니다.
대칭 차집합 함수를 사용하거나 map을 사용하여 풀 수 있습니다.

대칭 차집합

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int a, b; cin >> a >> b; vector<int> A(a), B(b), v; 
    for (int i = 0; i < a; ++i) cin >> A[i]; for (int i = 0; i < b; ++i) cin >> B[i]; sort(A.begin(), A.end()); sort(B.begin(), B.end()); 
    set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(v)); cout << v.size();
}

set_symmetric_difference 함수를 사용할 수 있으며 set_intersection과 사용법이 같습니다.
6792 KB, 64 ms를 소요합니다.

map

대칭 차집합은 결국 모두 입력 받아 중복된 값들은 제거하면 됩니다.
따라서 값을 입력 받아 map에 대입하는데, 이미 존재한다면 삭제합니다.

#include <iostream>
#include <map>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int N, M; map<int, bool> mp; cin >> N >> M;
    for (int i = 0; i < N + M; ++i) { int t; cin >> t; if (mp[t]) mp.erase(t); else mp[t] = 1; } cout << mp.size();
}

20768 KB, 244 ms를 소요합니다.
map을 사용하여 배열을 사용한 대칭 차집합 함수 코드보다 더 오래 걸립니다.

11478번 서로 다른 부분 문자열의 개수

문제 링크
중복되지 않은 요소의 개수를 도출해야 하므로 set을 사용합니다.

#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    string s; cin >> s; int l = s.length(); set<string> r;
    for (int i = 0; i < l; ++i) for (int j = 1; j < l - i + 1; ++j) r.insert(s.substr(i, j)); cout << r.size();
}

substr(start, length) 함수를 이용하여 문자열의 일부를 추출할 수 있습니다.
시작 위치부터 해당 길이만큼의 문자열을 반환합니다.
따라서 중첩반복문으로 구현하며 안쪽 반복문의 반복 조건은 j <= l - i로 설정합니다.