Post List

[BOJ] 백준 11652 카드

날짜:

[BOJ] 백준 11652 카드



문제 알고리즘 자체는 그냥 가장 많이 나오는 숫자를 출력하면 되는 간단한 문제 입니다.
하지만 이 문제의 정답률이 28%인 이유는, 바로 숫자의 범위가
 수는 -262보다 크거나 같고, 262보다 작거나 같다.
이기 때문 입니다.
일반적인 int는 사용할 수 없습니다. int는 4bytes 자료형이기 때문에 -2^32 ~ 2^32-1 밖에 표현을 하지 못하기 때문입니다. 따라서 8bytes 크기인 long long 자료형을 사용해야
2^64 까지 표현을 할 수 있습니다.

최대 정수의 개수는 100만개 입니다. 따라서 이것을 여러번 순회한다면 시간초과 오류가 날 것을 우려하여 find 함수를 사용하였는데 지금 생각해보니 도긴개긴 인것 같습니다.

소스 코드 : 

#include 
#include 
#include 
using namespace std;

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 int n;
 cin >> n;
    // 정수와, 등장한 횟수를 저장하기 위한 map 선언.
    // map은 key를 유일한 하나만 가지므로 map을 채택.
 map m;
    // p는 출력할(즉, tmp가 가장 작고 횟수는 가장 큰) pair임.
 pair p = { 0,0 };
 for (int i = 0; i < n; i++) {
  long long tmp;
  cin >> tmp;
  map::iterator it;
        // 입력받은 정수가 map에 존재 하는지 find.
  it = m.find(tmp);
        // map에 존재 한다면
  if (it != m.end()) {
            // 횟수 올리고
   it->second++;
            // 찾은 map의 등장 횟수가 p보다 더 크다면 바꿈.
   if (p.second < it->second) {
    p.first = it->first;
    p.second = it->second;
   }
            // 등장횟수가 같은경우, 정수가 작은게 있다면 작은것으로 바꿈.
   else if (p.second == it->second) { 
    if (p.first >= it->first) p.first = it->first;
   }
  }
        // map에 존재하지 않을 때
  else {
            // map에 삽입.
   m.insert(pair(tmp, 1));
   if (p.second == 0) {
    p.first = tmp;
    p.second = 1;
   }
            //p의 정수가 입력받은 정수보다 작다면 작은것으로 p를 바꿈.
   else if (p.second == 1 && p.first > tmp) {
    p.first = tmp;
   }
  }
  cin.ignore();
 }
 cout << p.first << endl;
 
}

댓글

댓글 쓰기