문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 $(-2)^{62}$보다 크거나 같고, $2^{62}$보다 작거나 같다.

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

입력

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

출력

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

풀이

문제에서 주어지는 수가 $(-2)^{62}$보다 크거나 같고, $2^{62}$보다 작거나 같기 때문에 int형이 아닌 long타입으로 받아야 한다. countin Sort를 생각해볼 수 있는데 여기서는 그걸로 해결할 수 없다. 따라서 선형탐색을 하면서 풀어야 하는데, N의 범위가 10만 이하이기 때문에 충분히 가능하다 생각하였다.

N의 길이만큼 long 타입으로 배열을 선언하여 입력을 받은 뒤 정렬을 수행한다. 그 다음 첫번째 인덱스부터 시작해서 count를 구해준다. 이전 값과 동일할 때 count+1를 해주고 아닐 때는 count = 1로 해준다. 이때 count 가 max보다 커지면 max를 count로 갱신해주고 출력해야하는 답 (ans) 도 새롭게 갱신해준다.

정렬을 먼저 한 이유는 위와같이 구하기 위함도 있고, 문제에서 동일한 갯수가 주어졋을 때 작은 값을 출력하라 햇으니 이와같이 구현해야 했다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		long[] cards = new long[n];

		for (int i = 0; i < n; i++) {
			cards[i] = sc.nextLong();
		}

		Arrays.sort(cards);

		// 초기 값
		long ans = cards[0];

		int count = 1;
		// 가장 많이 가지고 있는 갯수
		int max = 1;

		for (int i = 1; i < n; i++) {
			if (cards[i] == cards[i - 1]) {
				count += 1;
			} else {
				count = 1;
			}

			if (count > max) {
				max = count;
				ans = cards[i];
			}
		}

		System.out.println(ans);
	}

}