문제

BOJ 11652, 카드

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 여러 장의 카드가 있을 때, 가장 많이 가지고 있는 카드 중 숫자가 가장 작은 카드를 골라야 한다. 해당 문제에 가장 쉽게 접근하는 방법은 이진검색트리를 이용한 해시 자료구조라고 생각한다. 카드(정수)가 몇 개 있는지 개수를 세어 정렬하면 되기 때문이다. 추가로 이진탐색을 이용한 lowerbound, upperbound로 해당 정수가 몇 개 있는지 기록하고, 그중 제일 적은 수를 기록하는 방식도 가능하다.
• 정렬 하고 이를 순회하면서 개수는 가장 많지만, 같은 개수 중에서 가장 적은 수를 저장하는 풀이도 가능하다. 정렬로 해결하고 싶어 이 방법을 선택했다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
vector<ll> v;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	v.reserve(100'004);
	for (int i = 0; i < n; ++i) {
		long long num;
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	pair<long long, int> maxValue = {v[0], 0}; // number, cnt
	int cnt = 1;
	for (int i = 1; i < n; ++i) {
		if (v[i] == v[i - 1]) {
			++cnt;
			if (cnt > maxValue.second)
				maxValue = {v[i], cnt};
		} else {
			cnt = 1;
		}
	}
	cout << maxValue.first;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Long> nums = new ArrayList<>(100_004);
        for (int i = 0; i < n; i++) {
            Long num = Long.parseLong(br.readLine());
            nums.add(num);
        }
        nums.sort((a, b) -> {
            return a.compareTo(b);
        });
        Long[] maxValue = new Long[]{nums.get(0), 0l}; // value, cnt
        long cnt = 1;
        for (int i = 1; i < n; i++) {
            if (nums.get(i).equals(nums.get(i - 1))) {
                ++cnt;
                if (cnt > maxValue[1])
                    maxValue = new Long[]{nums.get(i), cnt};
            } else
                cnt = 1;
        }
        System.out.println(maxValue[0]);
    }
}