백준 11652번: 카드 (JAVA)

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

 

---

 

Python의 Counter가 그리워지는 날이다.

 

풀이

1. HashMap을 이용하여 각 원소마다 등장횟수를 기록한 후, entrySet를 통해 빈도가 최대일 때 원소값을 기록. 빈도가 동일할 땐 원소값이 작은 것을 기록하도록 해준다.

2. 인터넷에 더 널리 퍼져있는 풀이로, long[n]에(범위 유의!) 값을 하나하나 넣는다. 이후 정렬 후, 같은 값이 나올때마다 count를 1씩 늘려주면서 특정 값이 얼마나 나왔는지 횟수를 세준다. 만약 count가 기록되어있는 최대 빈도수보다 크다면(오름차순 정렬이므로 빈도가 같은 경우에 대한 고려를 할 필요가 없음.), 최고 빈도수 및 최다등장 원소를 바꿔준다.

 

내 생각에 풀이 1은 O(N) 풀이(entrySet() method도 구글링 해보니 O(1)인 듯하다)고, 풀이 2는 O(NlogN) 풀이다. 그런데 두 풀이는 유의미한 런타임 차이가 나진 않는다. 

 

배운 점

• .entrySet(), .keySet() 등 다양한 method를 배웠다.
• Python과 다르게, JAVA는 언제나 정수 범위에 대해 조심해야 한다. 이런 문제에서도 long 안 쓰면 문제 꼼짝없이 틀린다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Long, Integer> cardMap = new HashMap<Long, Integer>();
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			Long card = Long.parseLong(br.readLine());
			if (cardMap.containsKey(card)) {
				cardMap.put(card, cardMap.get(card) + 1);
			}else {
				cardMap.put(card, 1);
			}
		}
		long mostCommonCard = (long) Math.pow(2, 62) + 1; // 카드 값
		int mostCommonNum = 0; // 횟수
		for (Entry<Long, Integer> entry: cardMap.entrySet()) {
			if (mostCommonNum <= entry.getValue()) {
				if (mostCommonNum < entry.getValue() || mostCommonCard > entry.getKey()) {
					mostCommonNum = entry.getValue();
					mostCommonCard = entry.getKey();
				}
			}
		}
		System.out.println(mostCommonCard);
	}

}