백준 11652 / 카드

 

 

int	32bit ( 4byte )	-2^31 ~ 2^31 -1
long	64bit ( 8byte )	-2^63 ~ 2^63-1

카드에 적혀 있는 수가 -2^62보다 크고 2^62보다 같거나 작다고 했으므로 long의 범위를 사용할 것!!!

 

1. Map을 이용하기

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		Map<Long, Integer> map = new HashMap<>();
		int max=1;
		Long input;
		for(int i=0;i<num;i++) {
			input=Long.parseLong(br.readLine());
			if(map.containsKey(input)) {
				int val = map.get(input);
				if(val+1>max) {
					max=val+1;
				}
				map.put(input, val+1);
			} else {
				map.put(input, 1);				
			}
		}
		List<Long> list = new ArrayList<>();
		for(Map.Entry<Long, Integer> m : map.entrySet()) {
			if(m.getValue()==max)
				list.add(m.getKey());
		}
		Collections.sort(list);
		System.out.println(list.get(0));
		
	}
}

map.put()을 통해 값을 넣고 containsKey로 검사한다.

map.entrySet()으로 for문 안에 map의 key value를 하나씩 검사한다.

max값을 찾아내고 새로운 list에 넣어 정렬 후 첫번째를 추출한다.

 

 

2. int[] 배열 이용하기

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		long[] list = new long[num];
		for(int i=0;i<num;i++) {
			list[i]=(Long.parseLong(br.readLine()));
		}	
		Arrays.sort(list);
		
		int cnt=1;
		int max=1;
		Long value = list[0];
		for(int i=1;i<num;i++) {
			if(list[i]==list[i-1])
				cnt += 1;
			else
				cnt=1;
			if(cnt>max) {
				max=cnt;
				value=list[i];
			}
		}
		System.out.println(value);
	}
}

이 문제는 중복입력 가능한 숫자들 중 최대 입력된 숫자를 찾는 것이므로, 꼭 map을 이용하지 않아도 된다.

처음 값을 넣은 배열을 정렬하고 앞에서부터 배열을 비교해가면서 최대값을 갱신한다.

 

성능을 보면, long[]을 이용한 계산이 훨씬 빠르다. O(N)의 시간이면 되기 때문 일 것이다.