3. Map, Set

위의 STL 자료구조는 매우 자주 쓰이는 형태이므로 잘 정리해 두어야 한다.

Map

이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다.
이 자료구조의 경우는, vector나 배열과는 다르게 index를 활용하여 접근하는 것이 아니라 다른 자료형을 사용할 수 있는 것이다.
이 방법의 경우에는 검색, 삽입, 삭제 등의 속도가 빠른 편에 속한다.

선언 방법은 "map<key의 자료형, value의 자료형> 변수이름"이다.

Map을 사용해야 하는 경우는, 단순히 기존에 vector나 배열을 사용하는 방식처럼 index와 숫자를 매칭시킬 수 없는 상황이거나 연관있는 2개의 값을 매개하여 저장해야할 때 사용하게 된다.

 

사용방법은 다음과 같다.

 

m.size() : m의 원소의 개수
m.empty() : m의 노드의 개수가 0인지를 확인(스택과 큐에서의 역할과 비슷, 비어있으면 true 아니면 false를 반환)
m.find(key) : key에 해당하는 iterator를 반환 (만약 존재하지 않는다면, m.end에 해당하는 iterator 리턴)
m.earse(key) : key값에 해당하는 원소 삭제
m.insert(make_pair(key, value)) : 원소 추가 (단, m[key] = value 로도 원소를 추가할 수 있음)
m.begin() : 맨 첫번째 원소를 지시하는 iterator
m.end() : 맨 마지막 원소를 지시하는 iterator
m.count(key) : 해당 key값을 가지는 원소의 갯수(map에서는 활용할 일이 없으나 key가 중복될 수 있는 경우에 사용)

Set

이 알고리즘을 활용하기 위해서는 상단에 반드시 #include 을 선언해야 한다.
이 자료구조의 경우는 Map과 전반적으로 비슷하나 key값만 존재하고 value는 존재하지 않는다.
선언 방법은 "set<key의 자료형> 변수이름"이다.

Set을 사용해야 하는 경우는, 특정 값(Key)에 해당하는 자료를 자주 검색해야하는 경우에 사용하면 된다.

사용방법은 거의 Map과 유사하다.
s.size() : s의 원소의 개수
s.empty() : s의 노드의 개수가 0인지를 확인(스택과 큐에서의 역할과 비슷, 비어있으면 true 아니면 false를 반환)
s.find(key) : key에 해당하는 iterator를 반환 (만약 존재하지 않는다면, s.end에 해당하는 iterator 리턴)
s.erase(key) : key값에 해당하는 원소 삭제
s.inerst(key) : 원소 추가
s.begin() : 맨 첫번째 원소를 지시하는 iterator
s.end() : 맨 마지막 원소를 지시하는 iterator
s.count : 해당 key값을 가지는 원소의 갯수(set에서는 활용할 일이 없으나 key가 중복될 수 있는 경우에 사용)

 

위의 방식으로 접근할 수 있는 문제는 다음과 같다.

이 문제의 경우에는, 단순한 vector나 array를 활용하기에는 힘든 점이 존재한다.

 

왜냐하면 일반적으로 가장 쉬운 방법이 index와 입력 숫자를 연결시켜서 해당 숫자가 들어올 때마다 배열안의 숫자를 1씩 증기시키는 것이지만, 이 문제의 경우에는 입력되는 숫자가 매우 엄청 크기 때문에 메모리 초과가 발생하게 된다. pair하는 방법도 고려할 수 있으나, vector<pair<입력되는 숫자, 입력 횟수> >의 방법을 활용하게 되면, 숫자가 입력될 때마다 입력되는 숫자를 vector에서 확인하고 second 숫자를 증가시켜줘야한다. 이 경우에는 최악의 경우 O(n^2)이므로 시간초과가 발생하게 된다. 따라서 다른 방법을 고안해야 하는데, 그 방법중 하나가 map을 활용하여 입력하는 숫자와 입력횟수를 연결시켜주는 것이다. 이 경우에는 O(n)이므로 충분히 시간을 통과할 수 있게 된다.

 

해당하는 알고리즘을 코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    map<long long, int> map_data;
    map<long long, int>::iterator it;

    for(int i = 0; i < n; i++){
        long long temp;
        cin >> temp;
        if (map_data.count(temp) != 0){
            map_data[temp] += 1;
        }
        else{
            map_data[temp] = 1;
        }
    }

    long long max_check = -1;
    long long result_temp = -10e24;

    for(it = map_data.begin(); it != map_data.end(); it++){
        if (it ->second > max_check){
            max_check = it ->second;
            result_temp = it ->first;
        }
        else if(it ->second == max_check){
            if(it ->first < result_temp){
                result_temp = it ->first;
            }
        }    
    }

    cout << result_temp << "\n";
    return 0;
}

다만, 이 문제에서 숫자가 엄청나게 크므로 long long을 활용해서 처리해 주어야 한다는 점만 주의하면 된다.

추가적으로 위의 map과 set의 경우에는 index가 없으므로 iterator를 반복분에서 활용하게 된다.

BOJ 7785번(https://www.acmicpc.net/problem/7785) 처럼 역순으로 접근하는 것을 원하는 경우에는 reverse_order STL을 사용해주면 된다. 자세한 사용방법은 http://www.soen.kr/lecture/ccpp/cpp4/39-3-3.htm 를 참고하도록 하자. (시작을 begin이 아니라 rbegin, 끝을 end가 아니라 rend로 한다는 점에서 차이가 존재한다.)

 

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    set<string> s;
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        string name, value;
        cin >> name >> value;
        if(value == "enter"){
            s.insert(name);
        }
        else{
            s.erase(name);
        }
    }

    for(set<string>::reverse_iterator  it = s.rbegin(); it != s.rend(); it++){
        cout << *it << "\n";
    }
    return 0;
}