백준 9375: 패션왕 신해빈/MAP이용

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

---

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.

다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

---

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

int main() {
    int n; //테스트 횟수
    cin >> n;
    string name, cat;
    map<string, int> m;
    int cnt, ans; // 옷 종류 개수
    while (n--) {
        ans = 1;
        cin >> cnt;
        while (cnt--) {
            cin >> name >> cat;
            if (m.find(cat) != m.end()) {
                // 이미 포함 되어있는 경우
                m[cat] = m.at(cat) + 1;
            }
            else {
                // 포함이 안되어 있는 경우
                m.insert({ cat, 1 });
            }
        }
        for (auto iter = m.begin(); iter != m.end(); iter++) {
            ans *= (iter->second + 1);
        }
        cout << ans - 1 << '\n';
        m.erase(m.begin(), m.end());
    }

    return 0;
}

이 문제는 MAP을 이용하는 문제이다.

C++에서 MAP을 어떻게 이용하는지 알아보자

1. MAP이란?

→ map은 각 노드가 key와 value 쌍으로 이루어진 트리이다.

특히, 중복을 허용하지 않는다.

따라서 map은 first, second가 있는 pair 객체로 저장되는 데, first-key로 second-value로 저장된다.

2. MAP 기본 형태

map<key, value> 변수이름;
3. MAP 정렬

→ map은 자료를 저장할 떄 내부에서 자동으로 정렬한다.

map은 key를 기준으로 정렬하며 오름차순으로 정렬한다.

만약 내림차순으로 정렬하고 싶은 경우, 다음과 같이 사용하면 된다.

map<int, int, greater> 변수이름;
4. MAP 사용방법

(1) 헤더 포함

#include <map>

(2) map 선언하기

map<key type, value type> 이름;
map<string, int> m;

(3) map에 찾고자 하는 데이터가 있는지 확인하기

map에서 데이터를 찾을 때는 iterator를 사용한다.

데이터를 끝까지 찾지 못했을 경우, iterastor는 map.end()를 반환한다.

if(m.find("ding")!=m.end()){
cout << "find" << endl;
}
else{
cout << "not find" << endl;
}

(4) map에 데이터 삽입

map은 중복을 허용하지 않는다.

insert를 수행할 때, key가 중복되면 insert가 수행되지 않는다.

m.insert({"Cam", 300});

(5) 반복문 데이터 접근 (first, second)

• 인덱스 기반 반복문을 활용 → 인덱스 기반은 iterator를 활용하여 begin()부터 end()까지 찾는다.

for(auto iter= m.begin(); iter != m.end(); iter++)
{
cout <<iter->first<< " " << iter -> second << endl;
}
cout << endl;

• 범위 기반 반복문 활용한 예제

for(auto iter : m) {
cout << iter.first << " " << iter.second << endl;
}

(6) map에서 삭제하기

map에서 데이터를 삭제하기 위해 활용할 함수는 erase와 clear이다.

① 특정 위치의 요소 삭제

m.erase(m.begin()+2);

② key 값을 기준으로 요소 삭제

m.erase("Alice");

③ map의 모든 요소 삭제

1) erase 함수로 모든 요소 삭제하기 (map- begin ~ end)

m.erase(m.begin(), m.end());

2) clear 함수로 모든 요소 삭제하기

m.clear();