본문 바로가기
알고리즘 문제풀이/백준

[백준 11652] 카드

by m2162003 2021. 2. 25.

www.acmicpc.net/problem/11652

 

11652번: 카드

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지

www.acmicpc.net

숫자의 범위가 -2^62~2^62이므로 long long을 사용해야 한다.

 

 

1. map을 사용한 방법

map에 넣은 후 sort해주는 간단한 방법으로 풀 수 있다.

map을 소팅하는 방법은 pair<int, int>형 벡터로 선언해준 후 벡터를 정렬하는 방법이다.

메모리를 많이 사용한다.

#include <stdio.h>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

map<long long, int> mp;

bool cmp(const pair<long long, int> &p1, const pair<long long, int> &p2)
{
  if (p1.second == p2.second)
  {
    return p1.first < p2.first;
  }
  return p1.second > p2.second;
}
int main(void)
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    long long tmp;
    scanf("%lld", &tmp);

    mp[tmp]++;
  }

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

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

  printf("%lld\n", v[0].first);
  return 0;
}

 

2. 배열을 사용하는 방법

배열을 사용하지 않아도 풀 수 있다. 카드 값의 범위에 초점을 맞추지 않고 카드 개수에 초점을 맞춘다.

정렬한 후 각 숫자의 개수를 카운트한다.

 

항상 주의할 점은 마지막 경우의 수는 else 문을 거치지 않으므로 마지막에 조건을 한번 더 체크해줘야 한다.

#include <stdio.h>
#include <algorithm>

using namespace std;

long long arr[100000];
int main(void)
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    long long tmp;
    scanf("%lld", &arr[i]);
  }

  sort(arr, arr + n);
  int maxSum = 0, tmpSum = 1;
  int idx = -1;
  for (int i = 0; i < n - 1; i++)
  {
    if (arr[i] == arr[i + 1])
    {
      tmpSum++;
    }
    else
    {
      if (maxSum < tmpSum)
      {
        maxSum = tmpSum;
        idx = i;
      }
      tmpSum = 1;
    }
  }

  if (maxSum < tmpSum)
    idx = n - 1;
  printf("%lld\n", arr[idx]);
  return 0;
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1248] 맞춰봐  (0) 2021.03.01
[백준 16986]인싸들의 가위바위보  (0) 2021.03.01
[백준 148990] 경사로  (0) 2021.02.25
[백준 15591] Moo Tube  (0) 2021.02.17
[백준 1339] 단어 수학  (0) 2021.02.09

댓글