[BOJ_11652_RN] 카드 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/11652

문제 해결에 필요한 알고리즘 : map자료구조를 이용한 단순 구현문제

해설

주의해야 할 점 : 범위가  ~  이므로 C/C++ 기준 long long을 사용해야 풀 수 있음.

이 문제는 서로 다른 카드 중 가장 많은 카드를 찾는 문제이다. 범위가 작다면 카드를 배열의 인덱스로 이용해 갯수를 셀 수 있지만 범위가 크므로 배열은 사용이 불가하다. 그래서 map자료구조를 이용하면 된다. map자료구조를 이용해 데이터를 삽입하면서 갯수를 체크해준다. 이때마다 조건에 맞는 카드를 선택하면 된다.

다른 방법으로 정렬을 한뒤 순회하며 연결되어있는 갯수를 세 업데이트 하는 방법도 존재한다.

시간복잡도

map에 삽입을 하는데  만큼의 시간이 걸리고 이 삽입을 N번 반복하므로 최종 시간복잡도는  이다.

카드 코드 [ C++ ]

#include <cstdio>
#include <map>
typedef long long ll;
std::map < ll, int > mp;
int main() {
    int n, mx = 0, t;
    ll I;
    scanf("%d", &n);
    for (int i = n; i--; ) {
        ll m;
        scanf("%lld", &m);
        if (mx < (t = ++mp[m])) {
            I = m;
            mx = t;
        } else if (t == mx && m < I) {
            I = m;
        }
    }
    printf("%lld", I);
    return 0;
}