컴공댕이 공부일지
[ 맵과 셋 ] 자료 구조 Map & Set 알아보기 ( + 백준 9375번 패션왕 신해빈 ) 본문
📌 맵(Map)
맵은 키(key)와 값(value) 사이의 연관성을 나타내는 자료구조
맵은 일반적으로 이진 검색 트리를 기반으로 구현되고, 키의 *정렬된 순서를 유지합니다.
* 문제에 따라, 정렬된 순서가 필요없다면, 순서없는 맵도 사용하곤 하는데, 밑에서 문제 풀며 자세히 다룸 !!
맵(Map)의 주요 특징:
- 키와 값 사이의 일대일 관계 유지
- 마치 한영사전같은 느낌.. key는 사과, value는 apple. 둘이 짝지어져서 사과라는 키 값으로 apple을 서치 가능.
- 키는 중복 X. 즉, 각 키는 유일해야 합니다.
- 한영사전에 사과가 여러개일 순 없져 ㅎㅅㅎ
- 키를 기준으로 정렬됨
📌 셋(Set)
중복된 값을 허용하지 않는 자료구조
집합(set)과 유사하며, 고유한 값들을 저장하고 조회할 수 있음
셋도 내부적으로 이진 검색 트리를 기반으로 구현되며, 값들은 정렬된 순서로 저장됨.
셋(Set)의 주요 특징:
- 역시나 중복 허용 X. 모든 원소는 고유해야 합니다.
- 값들은 정렬된 순서로 유지됨.
그래서 셋에 이미 있는 값을 아무리 추가해도 그 값은 오로지 유일하게 하나입니다 !
각각의 원소들은 모두 고유해야하기 때문 :)
이러한 셋 자료구조는 특정 요소의 존재여부를 빠르게 파악하는 데서 진가를 발휘합니다.
셋에 제공되는 find 함수를 통해 이 셋에 값이 존재하는지 아닌지 확인 가능 ~
map set 활용 코드 [C++]
#include <iostream>
#include <map>
#include <set>
using namespace std;
int main() {
// 맵(Map) 예시
map<int, string> myMap;
// 맵에 값 추가
myMap[1] = "One"; // 키 : 1 , 값 : One
myMap[2] = "Two";
myMap[3] = "Three";
// 맵에서 값 찾기
cout << "Value corresponding to key 2: " << myMap[2] << endl;
// 셋(Set) 예시
set<int> mySet;
// 셋에 값 추가
mySet.insert(10);
mySet.insert(20);
mySet.insert(30);
// 셋에 값 삭제
mySet.erase(30);
// 셋에서 값 찾기
if (mySet.find(20) != mySet.end()) { // ..end() : 마지막 원소의 다음 위치를 가리키는 반복자. 셋의 끝부분.
cout << "Value 20 found in set" << endl;
// 즉, find로 찾은 위치가 셋의 마지막 다음(즉 끝)이 아니라면, 20은 존재하는 것 !
} else {
cout << "Value 20 not found in set" << endl;
}
// set의 출력과 역순 출력
cout << "Elements in the set: ";
for (const int& value : mySet) {
cout << value << " ";
}
// 역순으로 셋의 모든 요소 출력
for (auto it = names.rbegin(); it != names.rend(); ++it) {
std::cout << *it << "\n";
}
return 0;
}
+ ( 참고 )
- rbegin(): 컨테이너의 마지막 요소를 가리키는 역 반복자를 반환합니다.
- rend(): 컨테이너의 첫 번째 요소 앞을 가리키는 역 반복자의 끝을 반환합니다.
백준 9375번 패션왕 신해빈
실버 3
위에서 공부한 자료구조를 잘 떠올리며, 백준 문제 하나 풀어보면 좋을 것 같습니다 ~
아래에 제가 푼 정답 코드 첨부할게요 !
https://www.acmicpc.net/problem/9375
9375번: 패션왕 신해빈
첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.
www.acmicpc.net
정답 코드
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
unordered_map<string, int> clothes;
for (int i = 0; i < n; ++i) {
string name, type;
cin >> name >> type;
clothes[type]++;
}
int answer = 1;
for (const auto& pair : clothes) {
answer *= (pair.second + 1); // 각 종류별로 옷을 선택하지 않는 경우를 포함하기 위해 +1
// pair.second는 맵에서 특정 키-값 쌍에 대해 값(value)에 접근하는데 사용
}
// 알몸은 제외해야 하므로 -1
cout << answer - 1 << "\n";
}
return 0;
}
🔍 unordered_map
해시 테이블을 사용하기 때문에 평균적으로 O(1)의 시간 복잡도로 빠른 검색 속도를 보장.
데이터의 삽입, 삭제, 검색이 빈번하게 발생하고 정렬이 필요하지 않은 경우, unordered_map을 사용하는 것이 유용 !
그냥 맵을 사용해도 문제는 풀립니다 !
맵에는 위에서 설명했듯, key와 Value가 존재합니다 !
키 값에다가 의류 종류를 담고, 그 종류의 개수를 값에 담습니다.
여기서, 맵을 쓰는 이유는 맵은 중복이 없기 때문입니다.
옷의 타입별로 총 몇 벌인지, 즉, 안경은 몇 종류고, 상의는 몇 종류고 이런 내용을 맵이라는 자료구조에 담은거예요 !
hat이든 turban든 다 headgear 종류입니다.
우리가 알아야 할 정보는 헤드기어 종류의 옷이 총 몇 개 있냐는 거예요. 그래서 맵을 사용합니다.
아래 그림을 보면 더 이해가 쉬우실 것 같아요 !
위와 같은 과정으로 답을 계산할 수 있다 !
맵을 쓰는 이유는, 상의, 아이웨어, 헤드기어 등등의 옷 종류를 중복에 상관없이
개수만 카운트해 연산에 사용하기 위해서이다 ! :)
백준 7785번 회사에 있는 사람
실버 5
https://www.acmicpc.net/problem/7785
(정답코드)
#include <iostream>
#include <set>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
string name, status;
set<string> names;
cin >> n;
while(n--) {
cin >> name >> status;
if(status == "enter") {
names.insert(name);
} else {
names.erase(name);
}
}
// set 역순 출력 - rbegin : 마지막 요소, rend: 첫번째 요소 앞
for(auto iter = names.rbegin(); iter != names.rend(); iter++) {
cout << *iter << '\n';
}
return 0;
}
셋을 사용해 풀었다아 ~ set 요소들 출력하는 법도 익힘 !
입출력되는 데이터의 구조를 보고, 자료구조를 결정짓고,
적절한 자료구조를 선정해야, 보다 좋은 알고리즘을 짤 수 있다 :) (오늘 컴알 OT에서 주워들음 ㅎ)
자료구조 공부도 게을리하지 말쟈 화이팅 ! :D
'CS > 자료구조' 카테고리의 다른 글
[ 우선순위 큐와 힙 ] 완전 이진 트리, heap의 구현 ( + 백준 11279번 최대힙) (0) | 2024.03.28 |
---|