[해쉬] 1. 학급 회장

1. 학급 회장(해쉬)

 

설명

학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다.

투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다.

선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작성하세요.

반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.

입력

첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다.

두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 입력됩니다.

출력

학급 회장으로 선택된 기호를 출력합니다.

예시 입력 1 

15
BACBACCACCBDEDE

예시 출력 1

C

 

 

<<풀이>>

 

-나의 풀이-

 

시간복잡도 : O(N)

 

일단 HashMap이라는 것을 활용했다. 이 개념에 대해서는 공부한 적이 있어 어떻게 사용하는지는 어느정도 파악하고 있지만 명확하게 기억하고 있지는 못해서 다시 공부할 필요가 있다. 메서드와 정확하게 HashMap이 무엇인지 강사님 풀이를 보면서 파악하자.

 

나의 풀이는 어째어째 정보를 찾고해서 정답을 맞췄다.

 

constainsKey와 해쉬는 중복값을 허용하지 않기 때문에 같은 값이 들어오면 대체 되는 것을 이용했다.

 

그리고, 가장 최대 값을 가지고 있는 char을 가져올 때 keySet()메서드를 활용해서 구했다.

import java.util.*;

class Main {

    public char solution(int n, String chairman) {
        HashMap<Character, Integer> map = new HashMap();
        int max = 0;
        for(char x : chairman.toCharArray()) {
            if(map.containsKey(x)) {
                map.put(x, map.get(x) + 1);
            } else {
                map.put(x, 1);
            }
        }
        char answer = ' ';
        for(char a : map.keySet()) {
            max = Math.max(max, map.get(a));
        }

        for (char a : map.keySet()) {
            if(map.get(a) == max) {
                answer = a;
            }
        }

        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String chairman = in.next();
        System.out.println(T.solution(n, chairman));
    }
}

 

-강사님 풀이-

 

시간 복잡도 : O(N)

import java.util.*;

class Main {

    public char solution(int n, String chairman) {
        HashMap<Character, Integer> map = new HashMap();
        int max = 0;
        char answer = ' ';
        for(char x : chairman.toCharArray()) {
            map.put(x, map.getOrDefault(x,0) + 1);
        }
        for(char key : map.keySet()) {
            if(map.get(key) > max) {
                max = map.get(key);
                answer = key;
            }
        }
        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String chairman = in.next();
        System.out.println(T.solution(n, chairman));
    }
}

 

캬 ~ getOrDefault(x, 0) 이라는 메서드에 무릎을 탁치고 간다. 저렇게 하면 key가 존재하면 그 key의 value 값을 가져오고 존재하지 않으면 0으로 초기화 한다. 

이를 활용해서 하면 조금 더 코드를 깔끔하게 적을 수 있다.

 

<<추가 공부>>

 

map.get() // 특정 key값의 value 반환

map.getOrDefault() //key값이 존재하면 그 값의 value반환, 없다면 0으로 반환

map.keySet() //map이 가지고 있는 key값 나열

map.size() //map의 크기

map.remove('C') //map에 있는 key값 C를 제거하고  C의 value를 반환 map.size() 다시 해보면 1 감소