C++ Map사용법 [STL] + 백준 듣보잡

Map이란 -> C++STL 연관 컨테이너 중 하나

 

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

중복을 허용하지 않는다.

 

 

각 노드가 key와 value로 이루어진 트리

Map의 기본 형태 ->

 

map<key,value> map1

 

 

Map의 정렬->

 

Map은 자료를 저장할떄 내부에서 자동으로 정렬한다(key를 기준으로 오름차순 정렬)

 

Map사용법 ->

 

#include <map>포함

 

iterator(반복자)

->

stl에서  반복자는 포인터와 비슷하게 동작한다.반복자는 컨테이너에 저장된 원소를 순회하면서 접근하는 방법을 제공한다.또한, 컨테이너와 알고리즘을 하나로 동작하게끔 중간에서 인터페이스 역할을 한다.

 

STL의 모든 컨테이너는 각자의 반복자를 제공한다. 공통적으로는 멤버함수 begin() 와 end()가 순차열의 시작과 끝을 가리킨다. 주의할 점은 순차열의 시작과 끝에서 끝은 실제 원소가 아니라, 끝을 표시하는 원소이다.

 

Map에서 데이터 찾기->

 

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

데이터를 끝까지 못찾을 경우 iterator은 map.end()를 반환한다.

 

예시)

 if(iter != m.end()){  //map에서 데이터를 찾은경우
            cout << "find << '\n';
        }

else{ //못찾은 경우

    cout << "not_find << '\n';

}

 

Map에서 데이터 삽입->

 

m.insert({"A",1})

---

 

https://www.acmicpc.net/problem/1764

---

1764번: 듣보잡

 

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

---

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

---

해결방안 -> 듣도 못한 사람의 이름을 key값인 동시에 value값으로 지정한다. (N까지)

                 map iterator을 선언한 후 M만큼 반복문을 돌리면서 보도 못한 사람의 이름을 입력받는다.

                 만약 보도못한 사람의 이름을 Map에서 찾으면 듣도 보도 못한 사람이 되니깐 count증가시키고 

                 배열에 듣도 보도 못한 사람의 이름을 담아준다

 

-> 배열을 오름차순 한 후 출력한다

---

전체 소스 코드->

#include <iostream>

#include <map>

#include <string>

#include <algorithm>

 

using namespace std;

 

int main(void){

    map<string,string> m;

    int n;

    cin >> n;

    int M;

    cin >> M;

    for(int i = 0;i<n;i++){

        string temp;

        cin >> temp;

        m.insert(pair<string,string>(temp,temp));

    }

 

    int count = 0;

    map<string,string>::iterator iter;

 

    string arr[500010];

    int idx = 0;

 

    for(int i = 0;i<M;i++){

        string temp;

        cin >> temp;

        iter = m.find(temp);

        if(iter != m.end()){

            count++;

            arr[idx] = arr[idx] + temp;

            idx++;

        }

    }

   

    sort(arr,arr+idx);

   

    cout << count;

    cout << '\n';

    for(int i = 0;i<idx;i++){

        cout << arr[i] << '\n';

    }

}