[KOITP] 가장 많은 수

출처 : http://koitp.org/problem/SDS_PRO_2_4/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.1 초	512 MB	2362	459 (19%)	387

문제

N개의 정수가 주어진다. 이 중 가장 많이 등장하는 수를 구하시오. 만약 이런 수가 여러 개라면 작은 수를 출력하세요.

시간제한: 1초

입력

첫째 줄에는 정수의 개수 N이 주어진다. (1<=N<=1000000)

둘째 줄부터 N개 줄에 정수가 주어진다. 이 수의 절대값은 2^31 - 1 이하이다.

출력

가장 많이 등장하는 정수를 출력하시오.

힌트

입력 예제

4
1
2
3
3

출력 예제

3

< Comment >

 문제 자체는 매우 쉬워서 아무렇게나 풀어도 될 것이라고 생각했지만, 배열로 모든 숫자 범위를 저장할 경우 메모리가 부족하고, HashMap을 사용할 경우에는 속도가 워낙 느려서, 결국에 N+1 크기의 배열을 선언한 후, 마지막 숫자가 int 형의 마지막이 될 수 있도록 처리하여, 진행하였습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ManyNumber {
	
	public static int N = 0;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		int arr[] = new int[N + 1];

		arr[N] = Integer.MAX_VALUE;
		for (int i = 0 ; i < N ; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		int max = 0;
		int maxKey = 0;
		int count = 0;
		
		Arrays.sort(arr);
		for (int i = 0; i < arr.length - 1 ; i++) {
			
			if (arr[i] != arr[i+1]) {
				
				if (max < count + 1) {
					max = count + 1;
					maxKey = arr[i];
				}
				
				count = 0;
			} else {
				count++;
			}
		}
		
		
		bw.write("" + maxKey);
		bw.flush();
		bw.close();
	}
}