[BOJ-11652][C++] 카드

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 $-2^{62}$ 보다 크거나 같고, $2^{62}$보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

 

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

 

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

 

예제 입력 1 

5
1
2
1
2
1

 

예제 출력 1

1

 

예제 입력 2

6
1
2
1
2
1
2

 

예제 출력 2

1

 

알고리즘 분류

• 자료 구조
• 정렬
• 해시를 사용한 집합과 맵

 

문제 출처

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

11652번: 카드

 

---

 

문제 해결 방법

• 맵(@map@)을 이용하여 문제를 해결하였다.
• 입력값의 범위가 $-2^{62} \le N \le 2^{62}$ 이므로 자료형은 @long long@ 으로 선언해주어야 한다.

long long N, cardNo;
map<long long, int> cards;
vector<pair<long long, int>> counts;

• 맵을 직접적으로 정렬하는 것은 어렵기 때문에 맵의 키와 값을 벡터에 옮긴 후, 문제의 조건에 맞게 정렬을 시킨 후 결과를 출력하도록 하였다.

bool Compare(pair<long long, int> a, pair<long long, int> b) {
    if (a.second == b.second) {
        return a.first < b.first;    // 카드 빈도수가 같으면 카드 숫자를 오름차순으로 정렬
    }
    return a.second > b.second;    // 카드 빈도수를 내림차순으로 정렬
}

long long findMax(map<long long, int> m) {
    for (auto i : m) {
        counts.push_back({ i.first, i.second });
    }
    sort(counts.begin(), counts.end(), Compare);

    return counts[0].first;
}

void Output() {
    cout << findMax(cards) << '\n';
}

 

코드

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

long long N, cardNo;
map<long long, int> cards;
vector<pair<long long, int>> counts;

void Input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> cardNo;
        cards[cardNo]++;
    }
}

bool Compare(pair<long long, int> a, pair<long long, int> b) {
    if (a.second == b.second) {
        return a.first < b.first;    // 카드 빈도수가 같으면 카드 숫자를 오름차순으로 정렬
    }
    return a.second > b.second;    // 카드 빈도수를 내림차순으로 정렬
}

long long findMax(map<long long, int> m) {
    for (auto i : m) {
        counts.push_back({ i.first, i.second });
    }
    sort(counts.begin(), counts.end(), Compare);

    return counts[0].first;
}

void Output() {
    cout << findMax(cards) << '\n';
}

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

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• 실버IV

 

맵의 키와 값을 백터로 옮기기

• 맵의 키 또는 값을 정렬시키기 위해 맵의 키와 값을 벡터로 옮겨야 하는 경우가 있다.

 

방법 1

map<long long, int> m;
vector<pair<long long, int>> v;

for (auto i : m) {
    v.push_back({ i.first, i.second });
}

 

방법 2

map<long long, int> m;
vector<pair<long long, int>> v(m.begin(), m.end());