Tutorial: STL Map timer 1초 memory 32MB

map은 고유 키가 있는 키-값 쌍의 원소들로 이루어져 있는 데이터 컨테이너입니다.

map의 자료구조는 레드블랙트리로 구성되어 있기에 O(log n)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있습니다.

이와 비슷한 unordered_map은 해시테이블로 구성이되어 O(1)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있습니다. 

map의 기본적인 형태는 map<key, value>와 같고, key, value 값이 쌍으로 저장되는 형태를 띠어 key값으로 value를 찾을 수 있습니다.​

unordered_map​의 기본적인 형태는 unordered_map​<key, value>로 위와 마찬가지로 key값으로 value를 찾을 수 있습니다.​​

​세부적인 함수들의 구성은 아래 링크를 참조하시면 좋습니다.

map reference, unordered_map reference

우리가 기존 배열을 사용할 때는 인덱스가 무조건 0부터 N-1까지로 고정이 되어있었지만, 

map은 인덱스를 내 마음대로 정하고, 해당 공간만을 메모리에서 사용합니다.

구현은 아래와 같이 할 수 있지만, 아래 코드는 map을 아주 일부만 사용한 너무 간단한 예제이기에 위의 링크를 통해 자세한 사용법을 익혀보면 좋을 것 같습니다.

#include<cstdio>
#include<map>
using namespace std;
 
int main()
{
    map<int, int> m;
    m[0] = 3;
    m[7] = 8;
    m[-3] = 6;
 
    for(auto[key,value]:m){
        printf("%d %d\n", key, value);
    }
 
    return 0;
}

#include<cstdio>
#include<unordered_map>
using namespace std;
 
int main()
{
    unordered_map<int, int> m;
    m[0] = 3;
    m[7] = 8;
    m[-3] = 6;
 
    for(auto[key,value]:m){
        printf("%d %d\n", key, value);
    }
 
    return 0;
}

[문 제]

N개의 정수로 이루어진 수열에서 각 원소의 개수를 출력하는 프로그램을 작성하시오.