[Checkio] HOME. Sort Array by Element Frequency

Sort the given iterable so that its elements end up in the decreasing frequency order, that is, the number of times they appear in elements. If two elements have the same frequency, they should end up in the same order as the first appearance in the iterable.

Input: Iterable

Output: Iterable

Example:

frequency_sort([4, 6, 2, 2, 6, 4, 4, 4]) == [4, 4, 4, 4, 6, 6, 2, 2]

frequency_sort(['bob', 'bob', 'carl', 'alex', 'bob']) == ['bob', 'bob', 'bob', 'carl', 'alex']

 

Precondition: elements can be ints or strings

 

- 원소의 빈도수에 따라 내림차순 정렬

- 빈도수가 같으면 먼저 나온 요소가 먼저 나오게한다

 

내가 처음으로 풀었던 방식

def frequency_sort(items: list):
    p = {}
    for i in items:                 # items요소를 i로 받으며 반복
        if i not in p.keys():       # 딕셔너리에 i가 key값으로 없으면
            p[i] = items.count(i)   # i를 key로, items에서의 i의 개수를 value로 한 쌍
    # ↓ 딕셔너리 p를 value값을 기준으로 내림차순 정렬
    s2 = dict(sorted(p.items(), key = lambda x : x[1], reverse=True))
    # sorted함수를 거치면 list형이됨
    result = []
    for i in s2.keys():             # 정렬된 딕셔너리의 key값을 i로 받으며 반복
        a = []
        for _ in range(s2[i]):      # i값의 개수인 s2[i]만큼 반복해서 빈 리스트 a에 i를 추가
            a.append(i) 
        result.extend(a)            # extend를 사용해 리스트를 연결

처음에 set을 사용하려고 생각했다 근데 set을 쓰면 '먼저나온 요소가 먼저 나오게' 이것 때문에 더 복잡해지더라

set에 값들을 모두 오름차순 정렬를 하는 기능까지 있어서..

 

extend를 쓰니까 길이가 길어져서 줄일 방법을 막 찾아보다가 신기한걸 발견했다

extend랑 비슷한 방식이긴한데 sum을 이용하면 된다

def frequency_sort(items: list):
    p = {}
    for i in items:                 # items요소를 i로 받으며 반복
        if i not in p.keys():       # 딕셔너리에 i가 key값으로 없으면
            p[i] = items.count(i)   # i를 key로, items에서의 i의 개수를 value로 한 쌍
    
    s2 = sorted(p.items(), key = lambda x : x[1], reverse=True)
    r = [[i[0]]*i[1] for i in s2]
    return sum(r, [])

sum 함수는 sum(iterable[, start])의 형태를 띄고있고,  start와 iterable의 요소들을 더해 값을 반환하는 함수임

start의 디폴트값은 0이라서 sum([1,2,3,4]) = 0+1=2+3+4 가 된다

그런데 iterable에 2차원 리스트[[1,2],[3,4]]가 들어오면, [1,2]와 0을 더할 순 없어서 타입에러가 뜬다

그래서 sum([[1,2],[3,4]], []) 이렇게 start값을 [] 빈 리스트로 설정해 주면 편하게 리스트를 합칠 수 있다!

 

좀더 코드를 줄이려면

itertools의 chain함수와 collections 의 counter 함수를 알면 된다고 한다

 

개념

dict만들기 p={}  p["a"] = 5   ->  {"a" : 5}

p.keys()는 key값을 dict_keys 타입으로 가져옴. 안에 있는 값들을 따로 빼는건 안되는거같고 반복가능한 리스트로 쓰면 될듯

sorted는 list타입으로 반환, sorted(iterable, *, key=None, reverse=False) (기본형)

리스트 내포