2020 네이버웹툰 하계 인턴십(개발/리서치) 부분 코딩테스트 - 빈도 수 계산과 정렬.

2020 네이버웹툰 하계 인턴십(개발/리서치) 부분 코딩테스트 - 빈도 수 계산과 정렬.

---

< 문제 정의 >

주어진 정수형 배열에 저장되어 있는 원소들의 빈도수를 계산하고, 각 원소 별 빈도수 오름차순 + 원소 오름차순으로 정렬하여 출력하라. 예로써 int[] a = { 4, 5, 6, 5, 4, 3 } 이라는 배열이 input으로 입력되면, { 3, 6, 4, 4, 5, 5 } 로 정렬 된 결과가 출력된다. 정렬 및 출력 순서는 값의 크기보다 빈도수를 우선으로 한다.

 

---

< 문제 접근 >

우선 배열에 저장되어 있는 값들의 빈도수를 저장하기 위해서는 Key-Value 쌍의 'Map'을 사용해야 한다.  Key값은 중복을 허용하지 않기 때문에 각 원소 별 중복 데이터 수를 count 하기 위해 적합하고,  Key 값들을 오름차순으로 정렬하여 저장하기 위해서 HashMap을 사용하도록 한다. (TreeMap 또한 자연 순서로 Key값이 오름차순 정렬되기 때문에 TreeMap을 사용해도 무방하다.) 

 

문제 해결 순서는 다음과 같다.

1. 정수형 배열에 저장되어 있는 값들을 Key(배열의 원소)-Value(중복 개수) 형태의 쌍으로 하나씩 HashMap에 넣는다.
2. 위에서 만들어진 HashMap을 바탕으로 Value 기준(빈도수 count 기준) 으로 Key가 오름차순 정렬 된 List를 만든다.
3. Iterator를 선언하여 Value 기준으로 정렬 된 Key List를 순회하여 Value (빈도수) 만큼 출력한다.

 

---

< 문제 해결 >

public static void solution(int[] input) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 혹은 TreeMap

        for (Integer key : input) {
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        System.out.println(map);

        Iterator it = sortByValue(map).iterator();
        while(it.hasNext()){
            int temp = (int) it.next();
            for(int i=0 ; i<map.get(temp) ; i++){
                System.out.print(temp + " ");
            }
        }
    }

    public static List sortByValue(Map map){
        List<Integer> list = new ArrayList(); // 저장순서 유지, List는 Set과 다르게 저장순서가 유지된다.
        list.addAll(map.keySet()); // map에 저장된 Key들을 모두 List에 저장한다.

        Collections.sort(list,new Comparator(){

            public int compare(Object o1,Object o2){
                Object v1 = map.get(o1);
                Object v2 = map.get(o2);

                return ((Comparable) v1).compareTo(v2);
            }
        });
        //Collections.reverse(list); // 주석시 오름차순
        return list;
    }

먼저, 정수형 배열 input에 저장된 값들을 HashMap에 저장하기 위해 Key(정수형)-Value(정수형)의 HashMap을 선언해준다.

다음으로 input 배열을 처음부터 순회하면서, map.put(key, value) 로 HashMap에 Key-Value 쌍을 하나씩 넣어준다.

 

이 때, HashMap에 중복 된 키 값이 들어 올 경우, 새로 들어온 데이터가 기존의 데이터를 덮어쓰게 된다.

map.put(key, map.getOrDefault(key, 0) + 1) 한 줄로, 새로운 Key값이 들어왔을 때, 중복된 키가 없으면 default값에 1을 더한 값을 Value로 Key-Value 쌍이 새로 생성되고, 중복된 키가 존재 할 경우,  Key 값에 해당하는 Value를 가져와서 그 값에 1을 더한 값을 기존의 Key-Value 쌍 위에 새로운 Key-Value 쌍을 덮어쓰기한다. 이 방식으로 input 배열에서 중복 된 값이 Key로 들어갈 때, 기존의 Value가 1씩 더해지고 덮어씌워지면서 빈도수를 count 할 수 있다. 

 

위 과정을 거쳐 input 배열의 값들을 모두 HashMap에 넣고, map을 출력 해 보면 아래와 같은 Key(원소)-Value(빈도수 count)결과를 얻을 수 있다.

{3=1, 4=2, 5=2, 6=1}

 

다음으로, 위에서 구한 Key-Value 쌍을 Value 기준으로 정렬하기 위해서 sortByValue 함수를 구현한다.

Iterator에서 저장 순서를 보장받기 위해서 ArrayList를 생성하고, HashMap에서 생성한 Key들(3, 4, 5, 6)을 저장해 준다.

map.keySet() 함수를 통하여 Map에 저장 된 모든 Key를 가져올 수 있다.

list.addAll(map.keySet());

 

Comparable 인터페이스가 구현되지 않은 클래스를 정렬시키려면 Comparator 인터페이스를 구현한 클래스로 정렬시킬 수 있다. (Comparator 객체를 이용하면 Comparable 미구현 클래스도 정렬을 시킬 수 있다.)

아래와 같이 compare의 두 비교 대상을 map.get(Key) 함수로 HashMap에서 Key 값으로 Value를 가져온다, 즉 compare 대상은 Key-Value 쌍에서 Value(빈도수) 가 된다.

 

Collections.sort(list,new Comparator(){

            public int compare(Object o1,Object o2){
                Object v1 = map.get(o1);
                Object v2 = map.get(o2);

                return ((Comparable) v1).compareTo(v2);
            }
        });
//Collections.reverse(list); // 주석시 오름차순

 

마지막으로 Value 기준으로 오름차순 정렬 된 Key List를 Iterator를 통해서 처음부터 끝까지 반복하고,  Key들을 순회하면서 Value(빈도수) 만큼 출력해준다.

Iterator it = sortByValue(map).iterator();
        while(it.hasNext()){
            int temp = (int) it.next();
            for(int i=0 ; i<map.get(temp) ; i++){
                System.out.print(temp + " ");
            }
        }

 

---

< 결과 화면 >

input : { 4, 5, 6, 5, 4, 3 }