map

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

map 을 이용해서 문제를 푸는데 두 개의
집합의 차집합의 개수를 구하는 문제로

vector 의 이용의 검색으로 인한 시간이 걸리는 것을 막기 위해
map 을 사용하고자 했는데 map 에도 erase 와 같은
메서드가 존재하므로 보다 쉽게 차집합을 구할 수 있다.

• 원래 코드 (map 2개를 사용)

#include <iostream>
#include <map>

using namespace std;

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

    int N, M;
    cin >> N >> M;

    map<int, bool> A;
    map<int, bool> B;

    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        A[a] = true;
    }
    for (int i = 0; i < M; i++)
    {
        int b;
        cin >> b;
        B[b] = true;
    }

    int cnt = 0;
    for (auto iter = B.begin(); iter != B.end(); iter++)
    {
        if (A[iter->first] == false)
            cnt++;
    }
    for (auto iter = A.begin(); iter != A.end(); iter++)
    {
        if (B[iter->first] == false)
            cnt++;
    }

    cout << cnt;

    return 0;
}

• map erase 이용

#include <iostream>
#include <map>

using namespace std;

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

    int N, M;
    cin >> N >> M;
    int cnt = 0;

    map<int, bool> A;

    for (int i = 0; i < N + M; i++)
    {
        int a;
        cin >> a;
        if (A[a] == true)
        {
            A.erase(a);
        }
        else
            A[a] = true;
    }

    cout << A.size();

    return 0;
}

문자열 다루기

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

map 을 이용해서 문자열을 부분 문자열로 나눈 뒤
map 에 저장하면 쉽게 중복되는 것을 찾을 수 있다.

이때 문자열을 여러 개의 부분 문자열로 나누는 방법을 짜야되는데 어떻게 어떤 방식으로 되게 해야되는구나 를
떠올리고 햘려고 하니 python 마냥 arr[1:2] 식으로
어떻게 하지...? 하다가 생각해보니 substr 있었다.

• substr 사용

#include <iostream>
#include <string>
#include <map>

using namespace std;

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

    string S;
    map<string, bool> map_S;

    cin >> S;

    for (int i = 1; i <= S.length(); i++)
    {
        string temp = "";
        for (int j = 0; j < S.length(); j++)
        {
            if (j + i <= S.length())
            {
                temp = S.substr(j, i);
                map_S[temp] = true;
            }
        }
    }
    cout << map_S.size();
    return 0;
}

근데 굳이 substr 를 쓰지 않고 부분 문자열을 항상 정렬로
나오게 할 필요는 없기 때문에 두번째 for 문을 수정하면
간단하게 풀 수 있었다는 것을 알게 되었다...
(너무 문제 예시에 강박을 가지지 말자,,,)

#include <iostream>
#include <string>
#include <map>

using namespace std;

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

    string S;
    map<string, bool> map_S;

    cin >> S;

    for (int i = 0; i < S.length(); i++)
    {
        string temp = "";
        for (int j = i; j < S.length(); j++)
        {
            temp += S[j];
            map_S[temp] = true;
        }
    }
    cout << map_S.size();
    return 0;
}