[백준 알고리즘/BOJ] 자바(java) 11652번 카드

11652번: 카드

 

문제

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

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

입력

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

출력

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

 

 

처음엔 카드에 들어갈 수 있는 정수의 범위만큼 배열을 만들어, 어떤 정수가 출현할 때마다 그 정수를 인덱스로 가지는 배열을 1씩 증가시켜 가장 많이 가지고 있는 정수를 구하려고 했다. 하지만 정수의 범위가 -2^62~2^62이라 그 범위를 가지는 배열을 만드는 것부터 어렵고 (배열의 범위-> int형만 들어갈 수 있음) 가능하더라도 메모리 낭비가 심할 것 같았다. 그래서 배열을 오름차순으로 정렬시켜 같은 숫자가 연속된 위치에 있도록 하고, 배열을 순서대로 탐색해 연속된 숫자들의 count를 셌다. 숫자의 값이 변할 때마다 count와 countMax를 비교해 count가 더 크면 countMax값에 대입했다. 

 

처음엔 countMax의 초기값을 0으로 해놓고, 이클립스에서 잘 동작하는데 백준에서는 틀렸다고 나와서 몇분을 헤맸다. countMax의 초기값을 1로 변경하니 바로 맞았다고 떴다. 어차피 가장 첫번째 숫자를를 탐색하는 for문에서 if(countMax<count)를 만족해서 countMax가 1 이상으로 대입될텐데 왜 틀린 건지 이해가 안된다,,,,

 

package baekjoon;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class B_11652 {
	public static void main(String []args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long[] num = new long[N];
		for(int i=0;i<N;i++)
			num[i] = Long.parseLong(br.readLine());
		Arrays.sort(num);
		
		int count = 1; // for문을 돌며 각 정수의 횟수를 저장
		int countMax = 1; // 가장 많이 가지고 있는 정수의 출현횟수
		int indexMax = 0; // 가장 많이 가지고 있는 정수의 인덱스
		for(int i=1;i<N;i++) {
			if(num[i-1] == num[i]) 
				count++;
			else 
				count = 1;
			if(countMax < count) { 
				// 현재 숫자의 count가 countMax보다 크면 countMax에 count를 대입
				indexMax = i;
				countMax = count; 
			}
			//else if(countMax == count)
			// 오름차순으로 정렬했으므로 이전 숫자보다 현재 숫자가 더 큼. 즉 index 값 변경 x
		}
		System.out.println(num[indexMax]);
	}
}