[goormlevel] 이진수 정렬

문제

N개의 10진수 정수가 주어진다. 플레이어에게 정수를 그냥 정렬하는 것은 너무 쉽기 때문에, 아래 기준에 따라 정수를 정렬하기로 한다.

• 10진수 정수를 2진수로 나타냈을 때, 2진수에 포함된 1의 개수를 기준으로 내림차순 정렬한다.
• 1의 개수가 같다면, 원래 10진수를 기준으로 내림차순 정렬한다.

플레이어가 정수를 잘 정렬했을 때, 앞에서 K번째에 위치한 수는 어떤 수가 될지 구해보자.

입력

첫째 줄에 주어지는 정수의 수 N과 플레이어가 찾으려는 정수의 위치 K가 공백을 두고 주어진다.
둘째 줄에 정수 $a_{1}$, $a_{2}$, ... , $a_{N}$ 이 공백을 두고 주어진다.

• 1 $\leq$ N $\leq$ 500 000
• 1 $\leq$ K $\leq$ N
• 1 $\leq$ $a_{i}$ $\leq$ $2^{20}$

내 풀이

def binary_1count(x):
	return bin(x)[2:].count('1')

input1 = input()
input2 = input()

k = int(input1.split()[1])
list1 = list(map(int, input2.split()))

list1.sort(reverse=True, key=lambda x:(binary_1count(x), x))

print(list1[k-1])

코멘트

정렬 기준이 2가지(이진수에 들어있는 1의 개수 $\rarr$ 10진수)로 복잡해서 결국 다른 풀이를 참고했다.

• point 1 : 파이썬 내장함수 bin()이 10진수를 2진수로 변환해주는데, '0b1010'과 같은 형식의 string으로 반환해준다. 2진수 뿐만 아니라 6진수, 8진수로 변환해주는 함수도 있음.
• point 2 : map, lambda, list 메서드, string 메서드 등의 사용법을 폭 넓게 익히고 익숙해 질 것!
• point 3 : 리스트 메서드 sort의 key라는 인자를 사용할 수 있다. 여기서 lambda를 사용해 이진수에서 1의 개수를 세는 함수를 첫 번째 분류 기준으로, 두 번째 분류 기준을 원래의 10진수로 설정할 수 있다.

References

https://level.goorm.io/
https://dong8ee.tistory.com/m/80
https://mola2.tistory.com/2
https://art-coding3.tistory.com/6
https://brownbears.tistory.com/467
https://korbillgates.tistory.com/171
https://infinitt.tistory.com/122
https://docs.python.org/3/howto/sorting.html