[Codewars] 6Kyu, Simple Frequency Sort (Java, Python)

문제

https://www.codewars.com/kata/5a8d2bf60025e9163c0000bc

Codewars: Achieve mastery through coding challenge

 

문제 설명

In this Kata, you will sort elements in an array by decreasing frequency of elements. If two elements have the same frequency, sort them by increasing value.

Solution.sortByFrequency(new int[]{2, 3, 5, 3, 7, 9, 5, 3, 7});

// Returns {3, 3, 3, 5, 5, 7, 7, 2, 9}
// We sort by highest frequency to lowest frequency.
// If two elements have same frequency, we sort by increasing value.

More examples in test cases.

Good luck!

 

배열에 integer 값들 count순서대로 정렬하고, count가 같다면 오름차순 정렬하라는 뜻

 

 

 

 

어떻게 풀까?

• 정렬 문제라서 무지성으로 sort() 메소드를 써야겠다라는 생각을 함
• 근데 counting순서로 정렬을 할 수 있나..?? sort() 메소드 쓰기전에 배열의 값들 counting을 해야할 것 같음
• 일단 Map에 (int, count)으로 데이터를 모으고 얘네를 count순으로 정렬하고 배열에 담는 식으로 하면 될 것 같음
• 드가자

 

 

 

 

코드

자바 코드

package codewars._6kyu.Simple_frequency_sort_20220117;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Solution {

  public static int[] sortByFrequency(int[] array) {
    Map<Integer, Integer> countingMap = getCountingMap(array);
    List<Entry<Integer, Integer>> entryList = getSortedEntryList(countingMap);
    List<Integer> result = getListSortedByFrequency(entryList);

    return result.stream().mapToInt(x -> x).toArray();
  }

  private static Map<Integer, Integer> getCountingMap(int[] array) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int target : array) {
      map.put(target, map.getOrDefault(target, 0) + 1);
    }
    return map;
  }

  private static List<Entry<Integer, Integer>> getSortedEntryList(
      Map<Integer, Integer> countingMap) {
    List<Entry<Integer, Integer>> entryList = new ArrayList<>(countingMap.entrySet());
    entryList.sort((o1, o2) -> {
      if (o1.getValue().equals(o2.getValue())) {
        return o1.getKey() - o2.getKey();
      }
      return o2.getValue() - o1.getValue();
    });
    return entryList;
  }

  private static List<Integer> getListSortedByFrequency(List<Entry<Integer, Integer>> entryList) {
    List<Integer> result = new ArrayList<>();
    for (Entry<Integer, Integer> entry : entryList) {
      int key = entry.getKey();
      int value = entry.getValue();
      for (int i = 0; i < value; i++) {
        result.add(key);
      }
    }
    return result;
  }

  public int[] sortByFrequencyBestPracticeSolution(int[] array) {
    Map<Integer, Long> integerCountMap =
        Arrays.stream(array)
            .boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    return Arrays
        .stream(array)
        .boxed()
        .sorted(Comparator.<Integer, Long>comparing(integerCountMap::get)
            .reversed()
            .thenComparing(Comparator.naturalOrder()))
        .mapToInt(Integer::intValue)
        .toArray();
  }
}

Map으로 (int, count) 데이터를 만들고, EntrySet list를 통해 value(count) 순으로 정렬 (count가 같다면 key 오름차순), 그리고 result list에 하나씩 담아 배열로 변환하여 리턴

근데 Best Practice를 보니까 Stream으로 신박하게 해결했다. 참고하면 좋을듯?

Collectors.groupingBy(), Function.identity(), Collectors.counting(), Comparator.<Integer, long>comparing() 메소드들은 처음 보는 메소드들인데 알아두면 Stream에서 요긴하게 쓸 수 있을듯

 

 

 

파이썬 코드

def solve(arr):
    int_count_map = {}
    for integer in arr:
        int_count_map.setdefault(integer, 0)
        int_count_map[integer] = int_count_map.get(integer) + 1

    sorted_by_value_dict = sorted(int_count_map.items(), key=lambda x: x[1], reverse=True)

    result = []
    for items in sorted_by_value_dict:
        key = items[0]
        value = items[1]
        for i in range(value):
            result.append(key)

    return result


def solve_best_practice(arr):
    return sorted(sorted(arr), key=lambda n: arr.count(n), reverse=True)

파이썬으로도 풀어보자 해서 억지로 풀긴했다. 근데 BestPractice보니까 헛웃음이 나더라

자바에서 푼 것 처럼 dict에 (int, count)로 담고, count 내림차순으로 정렬했다.

근데 BestPractice보니까 그냥 개 쉽게 풀어버림.. 당황스럽네