[구름톤 챌린지] Day4 이진수 정렬

람다함수가 생각이 안나서 애먹은 문제였다..

sorted 에서는 정렬된 iterator 자체를 반환해주는 걸로 알고있어서 내부적으로 람다함수를 사용할 수 있다고 알고있다.

문제 그대로 따라가면 1. 2진수 '1' 개수를 기준으로 내림차수해준다음에 2. 개수가 같을 때 10진수 내림차순으로 정렬해주면 된다.

(SQL order by 부분이랑 상당히 생김새가 많이 닮았다고 생각했다.)

 

그리고, 더 고통받았던건 lambda 보다 더 자주 쓰지않은 bin 함수였었다.

1. 인자가 num(10진수) 가 들어간다는 점과

2. 리턴해준 문자열에서 '0b' 라는 접두사가 존재하는 것

위의 두가지가 해결된 이후 count('1') 을 통해 1의 개수를 쉽게 가져올 수 있었다.

 

위의 조건대로된 sorted가 리턴이 되었다면 리스트의 K - 1 인덱스를 가져오는 식으로 구현했다.

def check_bin(num):
    cnt_of_one = bin(num).count('1')
    return cnt_of_one


def pass_arr(arr, K):
    sorted_val = sorted(arr, key=lambda x: (-check_bin(x), -x))
    return sorted_val[K - 1]


N, K = map(int, input().split())
S = list(map(int, input().split()))

result = pass_arr(S, K)
print(result)

 

해설에서는 다음과 같은 과정을 통해 풀이했다.

1) 리스트에 있는 모든 원소를 bin함수를 통해 이진수로 변환시킨다.

2) 변환된 이진수에서 '1' 이 존재할 때 갯수를 for문으로 돌려서 카운팅 시켜준다.

3) 10진수 값과 2진수값을 리스트로 묶어서 그걸 또 리스트에 삽입시킨다.

4) 3)의 상태에서 내림차순으로 정렬한다.

 

튜플 또는 리스트로 묶어서 정렬하면 첫번째로 정렬기준이 맞춰지고 그다음 두번째 값을 보고서 정렬기준이 된다는 성질을 이용한 것이다.

그러나, 한계점에 대해서 명백하게 아래와 같이 서술되어 있다.

위의 풀이에서 정렬 과정이 한줄로 끝난 이유는 제가 코드를 작성할 때 [ 1의 개수, 10진수 값 ] 순서대로 newArr 에 집어넣었기 때문입니다. 파이썬에서는 정렬을 수행할 때 내부의 값이 리스트 등의 형태인 경우, 알아서 리스트의 각 위치를 기준으로 비교하여 정렬해줍니다.

즉 먼저 1의 개수 를 기준으로 내림차순 정렬하고, 이 값이 같은 경우 그 다음 원소인 10진수 값 을 기준으로 내림차순 정렬을 한 것입니다.

그런데, 만약에 [ 10진수 값, 1의 개수 ] 순서로 집어넣는다면 어떻게 될까요? 10진수 값 기준으로 먼저 정렬할테니 문제에서 묻는 답이 제대로 나오지 않을 것입니다. 또는 1의 개수 기준으로는 내림차순으로, 10진수 값 기준으로는 오름차순으로 정렬 하라는 등의 요구가 있다면요? 단순 내림차순 정렬로는 답을 구할 수 없을 것입니다.

따라서, 다중으로 정렬해주는 기준이 있을 때 lambda 함수로 정렬해주는 방법이 제일 깔끔하게 떨어진다 라고 생각하기로 했다.