[정렬] BOJ 11652번 카드

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

11652번: 카드

- 문제 파악

범위가 -2^62 ~ 2^62 인 정수가 N개 주어질 때, 개수가 가장 많은 정수를 출력하라, 개수가 같다면 그 중 제일 작은 정수를 출력하라

 

- 정답

무작위로 들어오는 수를 정렬을 통해서 개수를 세기 쉽게한다.

그 후 개수를 세어나가면 된다.

 

아래 항목들은 코드를 구현하면서 놓쳤던 부분이다.

1. 여유롭게 선언한 배열 이용하기 : N의 제한 사항은 1부터 10만이다. 그래서 나는 10만1개의 배열을 선언해서 문제를 풀었으나 반복문에서는 i+1을 항상봐야 했기 때문에 반복문의 범위를 N-1로 잡았다. 이렇게 되면 마지막 원소를 볼 수 가 없어서 제대로된 풀이를 할 수 없다.
2. 배열 초기화 : 전역변수로 배열을 선언하면 자동으로 0으로 초기화 된다. (지역변수일 경우 쓰레기값) 지금까지 풀었던 문제들은 대부분 양수를 다뤘으므로 배열에 대한 초기화를 따로 하지 않았는데, 이번 문제는 음수 양수 모두 사용하므로 0은 겹치는 수가 될 수 있다. 그러므로 문제에서 주어진 정수의 범위를 벗어나는 수로 초기화 해야한다.

 

#include "bits/stdc++.h"

using namespace std;

long long arr[100001];

bool cmp(pair<long long, int> a, pair<long long, int> b)
{
    if (a.second <= b.second) return false;
    return true;
}

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

    int n;
    cin >> n;

    fill(arr, arr + 100001, 4611686018427388002);

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);

    int pos = 0;
    long long min_key = arr[0];
    int max_val = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] != arr[i + 1])
        {
            int tmp = max_val;
            max_val = max(i - pos + 1, max_val);

            if (tmp == max_val)
                min_key = min(min_key, arr[i]);
            else
                min_key = arr[i];

            pos = i + 1;

        }
    }

    cout << min_key;

}