[구름톤 챌린지] 1주차 5일차 이진수 정렬

문제

---

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

 

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

$1$의 개수가 같다면, 원래 10진수를 기준으로 내림차순 정렬한다.

 

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

입력

---

첫째 줄에 주어지는 정수의 수 $N$과 플레이어가 찾으려는 정수의 위치 $K$가 공백을 두고 주어진다.
둘째 줄에 정수 $a_1, a_2, \cdots, a_N$이 공백을 두고 주어진다.

 

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

출력

---

기준에 따라 정렬된 정수 중, 앞에서 $K$번째에 위치한 수를 출력한다.

 

---

문제 접근 방식

---

파이썬의 bin함수를 이용하여 이진수로 만들어 준 뒤, 이를 map함수와 int함수를 활용하여 $1$의 개수를 세어주었다.

 

이 개수와 원래 숫자를 튜플로 만들어 새로운 리스트에 넣고, 이를 sort함수로 정렬해주었다.

 

---

정답 코드

---

# 이진수 정렬
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
num_li = list(map(int, input().rstrip().split()))
new_li = []
for i in range(N):
    new_li.append((sum(map(int, bin(num_li[i])[2:])), num_li[i]))

new_li.sort(reverse = True)
print(new_li[K-1][1])

 

---

특별히 배운 점

---

$2$진수의 성질을 이용하면 더 빠르게 할 수도 있을 것 같다. 파이썬의 bin함수는 string으로 반환하기 때문에 느리다.

 

만약 제한이 더 커진다면 $2$진수의 성질을 이용하는 다른 풀이를 강구해봐야 할 것이다.