백준 알고리즘 11652번 - 카드

그냥 구현하면 되는 거여서 엄청 쉬울줄 알았지만, 입력이 백만개나 되고,  생각보다 까다로웠던 문제(정답 비율이 27퍼인데는 이유가 있다)

구현은 그냥 그대로 했다. 배열에 수들을 입력받고, STL에 있는 sort 함수로 정렬을 해주었다.

그리고 현재 위치와 다음 위치에 있는 수가 같으면 count를 1 증가시켰고, 수가 다르면 count를 1로 다시 초기화하는 과정을 진행하였다. 여기서 시행착오가 많았는데 count를 초기화 하기 전에 지금 까지 나온 수 갯수중에 가장 많이 나온 것과 비교해주는 과정을 거쳐야 한다.

또 arr에 들어올 수 있는 수가 -2^62 부터 2^62까지 이므로 long long int로 구현해야 한다.

 

구현하는 종류의 문제이므로 설명보다는 소스코드에 있는 주석을 읽는 것이 나을 것같다.

 

소스 코드

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    long long int arr[1000001];
    int num;
    cin>>num;
    //배열에 입력받는다
    for(int i=1;i<=num;i++) scanf("%lld",&arr[i]);
    //arr베열을 정렬해준다
    sort(arr+1,arr+num+1);
    
    int max=1,count=1,idx=1;
    bool check=true;
    //배열을 돌면서 연속된 같은 수가 나오면 count에 1을 추가해준다
    for(int i=1;i<num;i++){
        if(arr[i]==arr[i+1]){
            count++;
        }
        //count가 지금까지 나온 수의 갯수중에 가장 크다면 그 갯수를 count로 바꿔준다 
        if(count>max)
         {
             max=count;
             idx=i;
         }
         //만약 연속적인 같은 수가 나오지 않는다면 count를 다시 1로 초기화한다.
         if(arr[i]!=arr[i+1]) count=1;
    }
    //가장 많이 나온 갯수를 출력한다
    printf("%lld",arr[idx]);
    return 0;
}

조금 난잡하게 짰지만, 그래도 로직 자체는 적당하고 1초 안에 해결을 패스했으므로 패스