[백준] 11652 카드 - HashMap(해시맵) JAVA

https://www.acmicpc.net/problem/11652

11652번: 카드

코드설명

HashMap 을 활용합니다.

 

 

 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000) 이기에, 해당 숫자보다 많은 정수를 찾기 위해 매번 값을 비교하면서 가져온다면 최악의 경우 100,000 * 100,000 O(N^2)의 시간복잡도가 나옵니다.

 

HashMap을 활용하여 O(1)의 시간만에 데이터의 개수를 조회하므로, 전체적으로 O(N)의 시간복잡도 안에 문제를 해결합니다.

코드

값을 입력받으면서 바로 체크합니다.

package algorhythm;

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

public class Main {
	public static int N, K;
	public static HashMap<Long, Integer> hashmap = new HashMap<Long, Integer>();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());

		long maxNum = 0;
		int maxCnt = 0;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			long num = Long.parseLong(st.nextToken());
			hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);
			
			if(hashmap.get(num) > maxCnt) {
				maxCnt = hashmap.get(num);
				maxNum = num;
			}			
			else if(hashmap.get(num) == maxCnt) {
				if( num < maxNum) {
					maxNum = num;
				}
			}
		}
		System.out.println(maxNum);
	}
}

 

EntrySet으로 HashMAp 순회하면서 가장 많은 숫자의 정수를 찾습니다.

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

public class Main {
	public static int N, K;
	public static HashMap<Long, Long> hashmap = new HashMap<Long, Long>();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			long num = Long.parseLong(st.nextToken());
			hashmap.put(num, hashmap.getOrDefault(num, (long) 0) + 1);
		}
		
		long maxNum = 0;
		long maxCnt = 0;
		for(Entry <Long, Long> entrySet : hashmap.entrySet()) {
			if(entrySet.getValue() > maxCnt) {
				maxCnt = entrySet.getValue();
				maxNum = entrySet.getKey();
			}
			else if(entrySet.getValue() == maxCnt) {
				if(entrySet.getKey() < maxNum) {
					maxNum = entrySet.getKey();
				}
			}
		}
		System.out.println(maxNum);
	}
}