[ 맵과 셋 ] 자료 구조 Map & Set 알아보기 ( + 백준 9375번 패션왕 신해빈 )

📌 맵(Map)

맵은 키(key)와 값(value) 사이의 연관성을 나타내는 자료구조
맵은 일반적으로 이진 검색 트리를 기반으로 구현되고, 키의 *정렬된 순서를 유지합니다.
 

* 문제에 따라, 정렬된 순서가 필요없다면, 순서없는 맵도 사용하곤 하는데, 밑에서 문제 풀며 자세히 다룸 !!

맵(Map)의 주요 특징:

1. 키와 값 사이의 일대일 관계 유지
2. 마치 한영사전같은 느낌.. key는 사과, value는 apple. 둘이 짝지어져서 사과라는 키 값으로 apple을 서치 가능.
3. 키는 중복 X. 즉, 각 키는 유일해야 합니다.
4. 한영사전에 사과가 여러개일 순 없져 ㅎㅅㅎ
5. 키를 기준으로 정렬됨

---

📌 셋(Set)

중복된 값을 허용하지 않는 자료구조
집합(set)과 유사하며, 고유한 값들을 저장하고 조회할 수 있음
셋도 내부적으로 이진 검색 트리를 기반으로 구현되며, 값들은 정렬된 순서로 저장됨.

셋(Set)의 주요 특징:

1. 역시나 중복 허용 X. 모든 원소는 고유해야 합니다.
2. 값들은 정렬된 순서로 유지됨.

그래서 셋에 이미 있는 값을 아무리 추가해도 그 값은 오로지 유일하게 하나입니다 !
각각의 원소들은 모두 고유해야하기 때문 :)
 
이러한 셋 자료구조는 특정 요소의 존재여부를 빠르게 파악하는 데서 진가를 발휘합니다.
셋에 제공되는 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번: 패션왕 신해빈

 
 
 
 
 
 
정답 코드

#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