Beakjoon 11652 카드

28 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11652

나의 풀이

이 문제에서 주의할 점은 N이 최대 100000이기 때문에 O(N^2)의 시간복잡도를 갖게되면 시간초과가 난다. 또한 숫자의 범위 또한 매우 크기 때문에 long long으로 정의해 주어야 문제를 해결할 수 있다.
위 조건을 만족하는 나의 풀이 방식은 다음과 같다.

1. 카드 값을 입력받고 입력받은 카드를 크기 순서대로 정렬한다.
2. 순서대로 정렬된 카드로 같은 카드의 개수가 각각 몇개인지 센다.
3. 가장 많이 가지고 있는 카드를 알아낸다.

풀이 코드 : 11652 카드

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

using namespace std;

bool compare(long long a, long long b){
    return a < b;
}

int main(){
    int N;
    vector<long long> input;
    long long num;
    scanf("%d", &N);

    
    for(int i=0;i<N;i++){
        scanf("%lld", &num);
        input.push_back(num);
    }
    sort(input.begin(), input.end(), compare);

    vector<pair<long long, int>> count;

    for(int i=0;i<input.size();i++){
        if(!count.empty() && count.back().first == input[i]){
            count.back().second++;
        }
        else{
            count.push_back(make_pair(input[i], 1));
        }
    }

    long long answer = input[0];
    int max_count = 0;
    for(int i=0;i<count.size();i++){
        if(max_count == count[i].second){
            if(answer > count[i].first)
                answer = count[i].first;
        }
        else if(max_count < count[i].second){
            max_count = count[i].second;
            answer = count[i].first;
        }
    }

    printf("%lld", answer);
}

채점결과