[백준] 11652번 : 카드 – JAVA [자바]

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

11652번: 카드

 

---

• 문제

 

 

---

• 문제 풀이

백준 11652번 카드는 실버 4 난이도의 정렬 및 해쉬 문제이다. 이 문제에서는 N개의 숫자들이 주어지고 가장 빈도수가 높은 숫자를 출력하면 된다. 문제에서 주어진 예제를 예시로 들어보겠다.

 

5개의 숫자가 주어지고 이 5개의 숫자들이 1 2 1 2 1이라고 해보겠다. 1이 3개, 2가 2개가 있으므로 가장 많이 나온 수는 1이다. 따라서 1을 출력하면 된다.

 

이 문제에서는 2가지의 추가 조건이 있다.

 

첫 째는 수가 -2^62 보다 크거나 같고, 2^62 보다 작거나 같다는 것이다. 따라서, int형을 쓰면 안 되고 long 형을 써야 한다.

 

두 번째 조건은 "가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다"이다. 따라서, 만약에 1이 3개, 2가 3개이면 더 작은 수인 1을 출력해야 된다는 뜻이다.

 

이 문제를 두 가지 방법으로 풀 것이다. 첫 째는 HashMap을 이용해서 푸는 것과 두 번째 방법은 간단한 배열만 이용해서 푸는 것이다.

 

풀이 1) HashMap을 이용한 풀이

우선 N개의 수를 입력받을 때 이 수를 HashMap에 저장한다. Key는 수, 그리고 Value는 이 수가 나온 개수를 저장한다. 이건 getOrDefault 함수를 이용하면 쉽게 구현할 수 있다.

 

수들을 다 입력받고 나면 이 HasmMap을 keySet 함수를 이용해서 iterate 한다. keySet 함수는 HashMap에 있는 키들을 집합 형태로 반환한다. 그리고 이 집합에 있는 키들을 map.get(key)를 통해서 더 값이 큰 것을 저장하고 마지막에 나와있는 수를 출력하면 된다.

 

풀이 2) 배열을 이용한 풀이

우선 사이즈가 N인 배열 arr을 만든다. 그리고 N개의 수들을 입력받을 때 다 이 배열에 저장한다. 그리고 Arrays.sort(arr)을 하면 자동으로 오름차순으로 정렬이 된다.  

 

그리고 두 번째 사이즈가 N인 배열 counts를 만든다. 이 배열은 배열 arr에 있는 똑같은 인덱스의 값의 개수를 저장한다.

 

첫 번째 예시를 다시 한번 보겠다. 1이 3개, 2가 2개가 있었다. 따라서, 배열들은 다음과 같다.

 

이때, counts가 가장 큰 값인 arr에 있는 값을 출력해 주면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드 1: HashMap

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Map<Long, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long m = Long.parseLong(br.readLine());
            map.put(m, map.getOrDefault(m, 0) + 1);
        }
        int max = -1;
        long num = 0;
        for (long l : map.keySet()) {
            if (map.get(l) > max) {
                max = map.get(l);
                num = l;
            } else if (map.get(l) == max) {
                num = Math.min(l, num);
            }
        }
        System.out.println(num);
    }

}

 

 

---

• 코드 2: 배열

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(arr);
        int[] counts = new int[n];
        counts[0] = 1;
        int maxCount = 1;
        long maxNum = arr[0];
        for (int i = 1; i < n; i++) {
            counts[i] = 1;
            if (arr[i] == arr[i-1]) counts[i] = counts[i-1] + 1;
            if (counts[i] > maxCount) {
                maxCount = counts[i];
                maxNum = arr[i];
            }
        }
        System.out.println(maxNum);
    }

}

 

 

---

• 성능 비교

아래에 있는 사진은 백준에서 걸린 시간을 보여준다. 배열을 이용하는 게 HashMap을 쓰는 것보다 더 빠른 듯하다.