백준 BOJ 다양한 해시맵(map) 활용 문제들 solution 220822

백준 BOJ 24411번 : Stamp Combinations

문제 난이도 : Silver I

알고리즘 분류 : 누적 합, 해시를 사용한 집합과 맵

 

길이 N인 수열에 대해, 앞의 부분합과 뒤의 부분합의 합으로 쿼리로 입력된 값을 만들 수 있는지 구하는 문제이다.

이 때 N x Q(쿼리의 수) ≤ 10^7이다.

 

누적 합을 사용하는 것은 확실해보이나, 누적 합을 사용하더라도 O(N^2)에 돌아간다.

따라서 시간 복잡도를 조금 더 개선할 방법을 찾아보아야 한다.

 

 

v_i를 1 ~ i번째 원소의 합이라고 하자.

그러면 뒤쪽 부분의 합은 v_N - v_i이고, 앞쪽 부분은 쿼리 값이 x라고 했을 때 x - (v_N - v_i)이다.

map을 활용하여 v_0 ~ v_N 값들을 모두 저장해두고 m[x - (v_N - v_i)]가 체크되어있는지만 확인하면 O(1) 시간에 확인이 가능하다.

반례로 가능한 것은 아래쪽의 그림과 같이 두 부분이 겹쳐버리는 것인데, 이런 경우는 continue로 넘기든 범위를 안 겹치게 설정해주어야 한다.

 

급하게 푸느라 그림이 조금 더러운데, 빗금(수열 전체의 앞 부분, 뒷 부분) 부분만 보면 대충 이해할 수 있을 것이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

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

    vector<int> v(N+1);
    for(int i=1; i<=N; i++) {
        int x; cin >> x;

        v[i] = v[i-1] + x;
    }

    unordered_map<int, bool> m;
    for(int i=0; i<=N; i++) m[v[i]] = true;

    while(M--) {
        int x; cin >> x;

        bool check = false;

        for(int i=0; i<=N; i++) {
            if(x - (v[N] - v[i]) > v[i]) continue;

            if(m[x - (v[N] - v[i])]) {
                check = true;
                break;
            }
        }

        if(check) cout << "Yes\n";
        else cout << "No\n";
    }
}

 

 

백준 BOJ 3557번 : Homo or Hetero?

문제 난이도 : Silver I

알고리즘 분류 : 트리를 사용한 집합과 맵

 

집합에 insert 또는 delete로 원소를 추가/제거할 때, 매 쿼리마다 집합이 어디에 속하는지를 구하는 문제이다.

문제에서 정의한 집합의 종류는 다음과 같다.

 

hetero : 원소가 두 개 이상이고 다른 원소가 존재하는 집합

homo : 원소가 두 개 이상이고 같은 원소가 존재하는 집합

both: hetero이면서 동시에 homo인 집합

neither : hetero도 아니고 homo도 아닌 집합

 

multiset을 이용하여 구현이 가능하다.

원소를 하나 erase할 때 주의할 점은 s.erase(x)와 같이 수행해주면 여러 개의 x를 가진 경우에도 모두 삭제가 된다.

따라서 s.erase(s.find(x))와 같이 작성해주어야 원소 x가 하나씩 삭제가 된다.

자세한 구현은 아래의 코드를 참조하는 편이 더 나을 것이다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int N; cin >> N;

    multiset<int> s;
    int cnt = 0;

    while(N--) {
        string str; cin >> str;
        int x; cin >> x;

        if(str == "insert") {
            if(s.count(x) == 0) cnt++;
            s.insert(x);
        }
        else if(str == "delete") {
            if(s.count(x) > 0) {
                s.erase(s.find(x));
                if(s.count(x) == 0) cnt--;
            }
        }

        if(s.size() >= 2 && s.size() > cnt && cnt >= 2) cout << "both\n";
        else if(s.size() >= 2 && s.size() == cnt) cout << "hetero\n";
        else if(s.size() >= 2 && cnt == 1) cout << "homo\n";
        else if(s.size() <= 1) cout << "neither\n";
    }
}

 

 

백준 BOJ 11313번 : Best Buddies

문제 난이도 : Silver II

알고리즘 분류 : 정렬, 해시를 사용한 집합과 맵

 

N명의 사람의 성과 이름이 주어지고, 이름을 last name의 사전순, last name이 같으면 first name의 사전 순으로 정렬한 뒤 앞에서부터 3명씩 같은 팀이 된다고 할 때, M개의 쿼리에 대해 한 사람의 이름이 주어지면 위에서 말한 정렬 순으로 다른 팀원 두 명의 이름을 구하는 문제이다.

 

먼저 정렬은 기준이 주어졌으므로 sort의 cmp 함수를 직접 정의하여 정렬해줄 수 있다.

이제 하나의 팀원의 이름에 대해 나머지 두 팀원의 이름을 구해주어야 하는데, N이 10만 이하이므로 O(N^2)과 같은 방법으로는 불가능하다.

따라서 map 2개를 선언하여, m[str] 값이 팀원 이름이 되도록 저장해주자.

그러면 O(1) 시간에 답을 찾을 수 있으므로 O(M)에 모든 쿼리를 처리해줄 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

bool cmp(pair<string, string> a, pair<string, string> b) {
    if(a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}

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

    int N; cin >> N;

    vector<pair<string, string>> v(N);

    for(int i=0; i<N; i++)
        cin >> v[i].first >> v[i].second;

    sort(v.begin(), v.end(), cmp);

    unordered_map<string, string> m1, m2;

    for(int i=0; i<N; i+=3) {
        string a = v[i].first + ' ' + v[i].second;
        string b = v[i+1].first + ' ' + v[i+1].second;
        string c = v[i+2].first + ' ' + v[i+2].second;

        m1[a] = b;
        m2[a] = c;

        m1[b] = a;
        m2[b] = c;

        m1[c] = a;
        m2[c] = b;
    }

    int M; cin >> M;
    cin.ignore();

    while(M--) {
        string str; getline(cin, str);

        cout << m1[str] << "\n" << m2[str] << "\n";
    }
}

 

 

백준 BOJ 16524번 : Database of Clients

문제 난이도 : Silver II

알고리즘 분류 : 해시를 사용한 집합과 맵

 

여러 이메일들이 주어질 때, 실제 사용자 수가 몇인지를 구하는 문제이다.

(이메일에서 @ 앞의 +가 나오면 + ~ @ 사이의 문자들은 모두 무시되며, @ 앞에 나오는 . 역시 무시된다.)

 

tmp라는 문자열에 무시되는 문자들을 제외하고 추가하여, map으로 중복 체크를 해주는 방식을 이용하자.

두 개의 bool 변수 a와 p를 이용하여 @와 +가 언제 나왔는지를 체크한다.

+가 나왔다면 @가 나오기 전까지는 모두 무시해주면 된다.

@가 나왔으면 그 뒤의 모든 문자를 추가해야한다.

@가 나오기 전의 .은 무시해주어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int N; cin >> N;

    map<string, bool> m;
    int ans = 0;

    while(N--) {
        string str; cin >> str;

        string tmp = "";
        bool a = false, p = false;

        for(int i=0; i<str.length(); i++) {
            if(str[i] == '@') {
                a = true;
                p = false;
            }
            else if(str[i] == '+') p = true;
            else if(p) continue;
            else if(str[i] == '.') {
                if(a) tmp += str[i];
                else continue;
            }
            else tmp += str[i];
        }

        if(!m[tmp]) ans++;

        m[tmp] = true;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 21396번 : 이진수 더하기

문제 난이도 : Silver II

알고리즘 분류 : 해시를 사용한 집합과 맵

 

주어진 N개의 수 중에서 두 수를 골라 받아올림이 없는 이진수 덧셈을 하여 M이 되는 조합의 수를 구하는 문제이다.

 

map을 사용하면 쉽게 풀 수 있다.

먼저 받아올림이 없는 이진수 덧셈은 xor 연산을 한 것과 같다.

이제 N개의 수를 앞에서부터 검사하며 m[x] 값을 더하고, 더한 이후에 m[M ^ x]에 1씩 더해주면 다음에 M ^ x가 N개의 수 중 하나로 들어올 경우 count가 된다.

이러한 방식으로 풀면 O(N) 시간에 모든 조합의 수를 찾을 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        unordered_map<int, int> m;
        int ans = 0;

        while(N--) {
            int x; cin >> x;

            ans += m[x];

            m[x ^ M]++;
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 21980번 : 비슷한 번호판

문제 난이도 : Silver II

알고리즘 분류 : 해시를 사용한 집합과 맵

 

알파벳으로만 이루어진 번호판에 대해 구성 문자와 길이가 같고, 대문자의 개수가 같으면 비슷한 번호판이라고 한다면 주어진 N개의 번호판 중 비슷한 번호판은 몇 쌍인지 구하는 문제이다.

 

먼저 번호판을 알파벳 순으로 정렬하는 것은 답에 영향을 주지 않는다.

또한, 대문자의 수만 count 해둔다면 모든 알파벳을 소문자로 바꾸어도 상관이 없다.

이를 이용하여 모든 번호판을 소문자로 바꾸고 정렬한 뒤, map을 <소문자 정렬 문자열, 대문자 개수> → 번호판 개수와 같이 설정한다.

이제 N개의 번호판을 순차적으로 검사하며 해당 번호판과 같은 문자열과 대문자 개수에 해당되는 map의 값만큼 답에 더해주면서 답을 구해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        map<pair<string, int>, int> m;
        int ans = 0;

        while(N--) {
            string str; cin >> str;

            int cnt = 0;

            for(int i=0; i<M; i++) {
                if(str[i] >= 'A' && str[i] <= 'Z') {
                    str[i] += 'a' - 'A';
                    cnt++;
                }
            }

            sort(str.begin(), str.end());

            ans += m[{str, cnt}];

            m[{str, cnt}]++;
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 4358번 : 생태학

문제 난이도 : Silver II

알고리즘 분류 : 해시를 사용한 집합과 맵

 

식물들의 목록이 주어질 때, 각 식물을 사전 순으로 출력하며 각 식물이 개수만큼 차지하는 비중을 백분위로 소수점 아래 4자리까지 구하는 문제이다.

 

map을 사용하여 어렵지 않게 해결할 수 있다.

이름이 나올 때마다 map[str] 값을 1씩 늘려주고, 마지막에 전체 나온 항목의 개수로 나눈 값 x 100을 하여 퍼센트 값을 구할 수 있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    string str;

    vector<string> v;
    map<string, int> m;
    int tot = 0;

    while(getline(cin, str)) {
        if(m[str] == 0) v.push_back(str);

        m[str]++;
        tot++;
    }

    sort(v.begin(), v.end());

    cout << fixed;
    cout.precision(4);

    for(int i=0; i<v.size(); i++)
        cout << v[i] << " " << (double)m[v[i]] * 100 / tot << "\n";
}

 

 

백준 BOJ 21208번 : Gratitude

문제 난이도 : Silver III

알고리즘 분류 : 정렬, 해시를 사용한 집합과 맵

 

3N개의 목록이 주어지고, 이들 중 가장 빈도가 높은 것이 먼저, 빈도가 같다면 마지막에 나온 것이 뒤 순서일 경우 먼저 나오도록 정렬하였을 때 앞의 M개의 목록을 구하는 문제이다.

 

map 2개를 사용하여 각각 나온 횟수, 그리고 마지막으로 나온 위치를 저장하여 정렬해주면 된다.

문제는 나온 목록의 종류가 M보다 작은 경우가 있으므로, min(v.size(), M)까지만 출력해주어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

unordered_map<string, int> m, idx;

bool cmp(string a, string b) {
    if(m[a] != m[b]) return m[a] > m[b];
    else return idx[a] > idx[b];
}

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

    int N, M; cin >> N >> M;
    cin.ignore();

    vector<string> v;

    for(int i=0; i<N*3; i++) {
        string str; getline(cin, str);

        if(m[str] == 0) v.push_back(str);

        m[str]++;
        idx[str] = i;
    }

    sort(v.begin(), v.end(), cmp);

    for(int i=0; i<min((int)v.size(), M); i++) cout << v[i] << "\n";
}

 

 

백준 BOJ 24653번 : Announcements

문제 난이도 : Silver III

알고리즘 분류 : 해시를 사용한 집합과 맵

 

N개의 광고가 v_i번째 날짜에 게재되고, M일마다 광고가 모두 수거될 때, 모든 광고를 보기 위해서 학교에 가야하는 날의 최소 수를 구하는 문제이다.

 

M일에 광고가 수거된다면 1 ~ M-1번째 날에 광고를 보러가면 된다.

즉, N개의 값들을 M으로 나눈 몫이 몇 가지 종류인지를 물어보는 문제임을 알 수 있다.

따라서 map을 이용하여 v_i / M이 나왔던 값인지를 체크하고 만약 나오지 않았다면 답에 1을 더해주는 방식을 반복하면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int N; cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    int M; cin >> M;

    unordered_map<int, bool> m;
    int ans = 0;

    for(int i=0; i<N; i++) {
        int x = v[i] / M;

        if(!m[x]) ans++;

        m[x] = true;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 18295번 : Ants

문제 난이도 : Silver III

알고리즘 분류 : 해시를 사용한 집합과 맵

 

주어진 수들 중에서 나타나지 않은 가장 작은 0 이상의 정수를 찾는 문제이다.

이 때 매우 큰 정수가 입력으로 들어올 수 있다.

 

map을 이용하여 정수들의 입력 여부를 체크할 것인데, 매우 큰 정수가 입력될 경우 오류를 발생시킬 수 있으므로 일단은 문자열로 입력받은 뒤 특정 자리수 이상의 길이를 가질 경우 continue 처리를 해준다.

그 외의 경우에는 map에 기록을 해주고, 그 다음 0부터 검사하면서 map 값이 false인 최초의 정수에 대해 출력을 해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int N; cin >> N;

    unordered_map<int, bool> m;

    while(N--) {
        string x; cin >> x;

        if(x.length() > 7) continue;

        m[stoi(x)] = true;
    }

    for(int i=0; ; i++) {
        if(!m[i]) {
            cout << i << "\n";
            break;
        }
    }
}

 

 

백준 BOJ 5588번 : 별자리 찾기

문제 난이도 : Gold IV

알고리즘 분류 : 브루트포스

 

N개의 별의 좌표가 주어지고, 이들이 같은 거리만큼 평행이동을 했으며 N개보다 많은 M개의 별이 주어질 때 N개의 별이 얼마만큼 평행이동을 했는지를 구하는 문제이다.

 

N이 500 이하라서 브루트포스 알고리즘으로 풀린다.

map에 0번째 별을 기준으로 다른 별들의 간격을 저장하고, M개의 별들 중에 이러한 간격을 모두 가지는 것이 있다면 그 별이 0번째 별인 것이므로, 아까의 0번째 별의 좌표에서 얼마나 이동했는지 계산해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int N; cin >> N;

    vector<pair<int, int>> v(N);

    for(int i=0; i<N; i++)
        cin >> v[i].first >> v[i].second;

    map<pair<int, int>, bool> m;

    for(int i=0; i<N; i++)
        m[{v[i].first - v[0].first, v[i].second - v[0].second}] = true;

    int M; cin >> M;

    vector<pair<int, int>> u(M);

    for(int i=0; i<M; i++)
        cin >> u[i].first >> u[i].second;

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

        for(int j=0; j<M; j++) {
            if(m[{u[j].first - u[i].first, u[j].second - u[i].second}]) cnt++;
        }

        if(cnt >= N) {
            cout << u[i].first - v[0].first << " " << u[i].second - v[0].second << "\n";

            break;
        }
    }
}