[BOJ] 백준 11652번 - 카드

문제

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

11652번: 카드

 

풀이

1. 변수 값 범위 확인

문제에서 주어지는 요구조건을 확인한 뒤, 값의 범위에 맞는 타입으로 변수를 선언해야 한다.

카드 번호 : (-2^62 <= N <= 2^62) => long
카드 개수 : (1 <= N <= 100,000) => int

*int 표현 범위 : –2,147,483,648 ~ 2,147,483,647
*long 표현 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

 

2. [카드번호(key) : 개수(value)] 쌍을 HashMap에 저장, 개수(value) 누적

map.getOrDefault(key, defaultValue) 
: Map에 key가 존재할 경우 value를 반환, 존재하지 않을 경우 defaultValue 값을 반환한다.
아래 코드는 map에 key가 존재할 경우, 해당 카드의 (value값 + 1)을 value로 저장하고, map에 key가 존재하지 않을 경우 0 + 1 = 1을 value로 저장한다.

HashMap<Long, Integer> map = new HashMap<>();

for (int i = 0; i < N; i++) {
    long val = sc.nextLong();
    map.put(val, map.getOrDefault(val, 0) + 1);
}

 

3. HashMap 키와 값을 기준으로 정렬

컬렉션을 정렬하는 Collections.sort() 메서드는 List인터페이스를 구현하는 클래스만 매개변수로 올 수 있기 때문에 HashMap의 key값을 요소로 가지는 ArrayList객체를 생성한다.
Collections.sort() 메서드 호출 시 Comparator을 새로 생성하고 compare() 메서드를 오버라이딩해서 List내 요소들의 비교기준을 선언해둔다. (key : 카드번호, value : 개수)
= 카드개수가 같을 경우 카드번호 오름차순으로 정렬, 카드개수가 다를 경우 카드개수 내림차순으로 정렬.

List<Long> keySetList = new ArrayList<>(map.keySet());

Collections.sort(keySetList, new Comparator<Long>() {
    @Override
    public int compare(Long key1, Long key2) {
        Integer val1 = map.get(key1);
        Integer val2 = map.get(key2);

        if (val1.equals(val2)) {
            return key1.compareTo(key2);
        }else{
            return val2.compareTo(val1);
        }
    }
});

 

HashMap에서 Map.Entry타입으로 가져와서 key-value쌍으로 구성된 List를 생성한 뒤, Comparator에서 map.get(key) 할 필요없이 Entry객체에서 바로 key, value값을 추출해 비교해도 된다.

List<Map.Entry> entryList = new ArrayList<>(map.entrySet());

 

4. Integer 타입 값 비교

변수가 int 타입일 경우 '=='을 사용해도 되지만, Integer 래퍼 클래스일 경우에 '=='를 사용하면 참조비교가 수행되기 때문에 Integer 타입에서 값 비교를 수행하고자 할 때는 equals() 함수를 사용해야 한다.

// 틀린 예 (실행결과 "틀렸습니다." 나옴)
public int compare(Long key1, Long key2) {
    Integer val1 = map.get(key1);
    Integer val2 = map.get(key2);

    if (val1 == val2) {
        return key1.compareTo(key2);
    }else{
        return val2.compareTo(val1);
    }
}


// 올바른 예 ("맞았습니다!!")
public int compare(Long key1, Long key2) {
    Integer val1 = map.get(key1);
    Integer val2 = map.get(key2);

    if (val1.equals(val2)) {
        return key1.compareTo(key2);
    }else{
        return val2.compareTo(val1);
    }
}

 

코드

import java.util.*;

// HashMap 정렬
public class Main {
    public static void main(String[] args) throws java.lang.Exception {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        HashMap<Long, Integer> map = new HashMap<>();

        for (int i = 0; i < N; i++) {
            long val = sc.nextLong();
            map.put(val, map.getOrDefault(val, 0) + 1);
        }

        List<Long> keySetList = new ArrayList<>(map.keySet());
        // 카드 개수 내림차순 → 카드 넘버 오름차순
        Collections.sort(keySetList, new Comparator<Long>() {
            @Override
            public int compare(Long key1, Long key2) {
                Integer val1 = map.get(key1);
                Integer val2 = map.get(key2);

                if (val1.equals(val2)) {
                    return key1.compareTo(key2);
                }else{
                    return val2.compareTo(val1);
                }
            }
        });

        if (keySetList.size() > 0) {
            System.out.println(keySetList.get(0));
        }
    }
}