int migratoryBirds(vector<int> arr) {
    // sort로 id순 정렬
    sort(arr.begin(),arr.end());

    int check = 1;  // id당 갯수 카운트
    int comp = 1;   // 이전 최대수와 비교
    int id = 0;     // 최대수를 가진 id > 반환
    
    for(int i =1; i<arr.size(); i++)
    {
        // 원소가 바뀌었다면 해당 id의 카운트가 끝났다는 뜻이고,
        // 직전 최대 갯수와 비교를 진행할 수 있다.
        // 단, 마지막 id인 5는 마지막 원소에 도달했을 때 비교
        if(arr[i] != arr[i-1] || i == arr.size()-1)
        {
            if(check > comp)
            {
                id = arr[i-1];
                comp = check;
            }
            check = 1;
        }
        check++;
    }
    return id;
}

string dayOfProgrammer(int year) {
    bool leap = false;
    bool julian = false;
    
    if(year < 1918)
        julian = true;
    if(julian && year % 4 == 0)
        leap = true;
    if(!julian && year % 400 == 0)
        leap = true;
    if(!julian && year % 4 == 0 && year % 100 != 0)
        leap = true;
        
    if(year == 1918){
        return "26.09.1918";
    }
    if(leap){
            return "12.09."+to_string(year);
    }
    else{
            return "13.09."+to_string(year);
    }
}

// 맵 활용
int sockMerchant(int n, vector<int> ar) {
    map<int,int> map;
    for(size_t i = 0; i<n; i++){
        if(map.find(ar[i]) != map.end())
        {
            map[ar[i]]++;
        }
        else{
            map.insert(make_pair(ar[i],1));
        }
    }
    
    int answer = 0;
    for(auto iter: map){
        answer += iter.second / 2;  // 소숫점을 버린 값만 계산된다
        cout << iter.second << '\n';
    }

    return answer;
}

// 메모이제이션
int sockMerchant(int n, vector<int> ar) {
    int temp[101] = {}; // 양말색 101가지
    
    for(size_t i = 0; i< ar.size(); i++){
        temp[ar[i]]++;
    }
    
    int answer = 0;
    for(auto iter : temp){
        answer += iter /2;
    }
    return answer;
}