BOJ 11652) 카드 (C++)

11652번: 카드

문제를 처음 봤을 때 바로 map이 떠올라서 map으로 풀었는데 정렬로 푸는 방법이 있다는 걸 알게 되서 정렬로도 풀어 보았다.

# map 이용한 풀이

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N;
    map <long long, int> m;
    cin>>N;
    while(N--){
        long long s;
        cin>>s;
        if(m.find(s)!=m.end()){
            m[s]+=1;
        } else {
            m.insert({s, 1});
        }
    }
    int ans=0;
    long long temp;
    for(auto iter = m.begin(); iter!=m.end();iter++){
        if(iter->second >ans){
            ans=iter->second;
            temp=iter->first;
        } else if(iter->second == ans){
            if(temp>iter->first){
                ans=iter->second;
                temp=iter->first;
            }
        }
    }
    cout<<temp;
}

들어오는 수를 키값으로 하고 value를 횟수로 하여 해결했다. 입력을 다 받고 map을 순회하면서 value가 가장 크면서 key값이 가장 작은 key값을 찾고 이를 출력한다. (2^62가 long long으로 커버가 되는지 기억이 안나는데 찾아보기 귀찮아서 key를 string으로 했다가 나중에 key 크기 비교를 해야 한다는 걸 알고 뒤늦게 찾아보고 수정해야 했다.) 

 

# sort 이용한 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N, curcnt, maxcnt=0;
    long long maxval=0, curval=0;

    cin>>N;
    
    vector<long long> v(N);

    for(int i=0;i<N;i++){
        cin>>v[i];
    }

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

    curval=v[0]; maxval=v[0]; curcnt=1;
    for(int i=1;i<N;i++){
        if(curval!=v[i]){
            if(maxcnt<curcnt){
                maxval=curval;
                maxcnt=curcnt;
            }
            curval=v[i];
            curcnt=1;
        }else if(curval==v[i]){
            curcnt++;
        }
    }
    if(curcnt>maxcnt) maxval=curval;
    
    cout<<maxval;

    return 0;
}

(https://blog.encrypted.gg/966?category=773649 해당 강의의 풀이를 참고했다)

벡터로 일괄적으로 입력을 받은 후 정렬한 다음 작은 수 부터 차례로 등장 횟수를 카운트한다. 카운트하고 있는 수가 변할 때, 카운트한 횟수가 최대 카운트보다 크면 최대 카운트 값을 변경하고 값을 저장한다. 

map으로 푸는 것과 달리 sort를 이용해서 풀 때는 마지막 값에 대한 별도 처리가 필요했다. 반복문만 돌고 끝내면 정렬 후 마지막 값이 카운트되지 않아 오답이 된다.