BOJ) 카드

카드

11652번: 카드

풀이

 

문제를 보고 바로 떠오른 방법은 Map을 이용해서 푸는 방법이었다.

Map을 통해 해당 카드가 몇 번 나왔는지 카운트 한 다음, value를 통해 key를 정렬하는 방법이다.

문제의 조건에 따라, 나온 횟수가 같은 경우에는 카드의 숫자가 최소인 것부터 정렬해서 리스트의 가장 앞 부분에 있는 값을 리턴했다.

바로 맞기는 했지만, 효율이 너무 좋지 않았다. 메모리와 속도 측면도 그렇고, Map을 사용하지만 어차피 Key값을 저장하기 위해서 List를 사용해야하는 부분도 그렇고, List로 바로 푸는 것도 괜찮을 것 같아서 바로 풀었다.

 

Lits에 값들을 저장하고 오름차순으로 저장한 다음에, 해당 숫자들이 몇번 나오는지 카운트 해줬다.

값들은 오름차순을 증가하고 있기 때문에, 카운트가 더 많은 경우에만 답을 최신화 해주었다. (왜냐하면 count가 같은 경우에는 앞서 나온 값들이 답이 되기 때문에)

 

결론적으로는 메모리를 덜 잡아먹었다.

하지만, for문을 통해 직접 count를 하면서 속도는 유사했다. (값이 더 많아지면 커질 것 같다.)

두 개의 풀이를 봤을 때, List로 푸는게 더 간단하지만, HashMap의 Key를 Value 값에 따라 정렬하는 방법도 알아두면 좋을 것 같다.

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class CardSort_11652 {
    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        HashMap<Long, Integer> cardMap = new HashMap<>(); // HashMap을 이용한 풀이(메모리를 조금 더 사용함)
        for(int i=0; i<n; i++) {
            long key = Long.parseLong(br.readLine());
            if(cardMap.containsKey(key)) {
                cardMap.replace(key, cardMap.get(key)+1);
            } else {
                cardMap.put(key, 1);
            }
        }
        List<Long> keySetList = new ArrayList<>(cardMap.keySet());
        Collections.sort(keySetList, new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                int cnt1 = cardMap.get(o1);
                int cnt2 = cardMap.get(o2);
                if(cnt1 < cnt2) {
                    return 1;
                } else if(cnt1 == cnt2) {
                    return o1 > o2? 1 : -1;
                }
                return -1;
            }
        });
        System.out.println(keySetList.get(0));
	}
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class CardSort_11652 {
    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        List<Long> cardList = new ArrayList<>();    // List를 활용한 풀이, 공간은 덜 사용하지만 속도는 아주 조금 더 느림
        for(int i=0; i<n; i++) {
            cardList.add(Long.parseLong(br.readLine()));
        }
        Collections.sort(cardList);

        long answer = cardList.get(0);
        int answerCnt =0;

        long prev = answer;
        int prevCnt =0;
        for(long num : cardList) {
            if(num == prev) {
                prevCnt++;
            } else {
                if(answerCnt <prevCnt) {
                    answer = prev;
                    answerCnt = prevCnt;
                }
                prev = num;
                prevCnt =1;
            }
        }
        if(answerCnt < prevCnt) {
            answer = prev;
        }
        System.out.println(answer);
    }
}