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

문제5. 이진수 정렬

구름LEVEL

---

---

문제 해결 방법

2진수로 나타냈을 때의 1의 개수가 많은 순으로 정렬하되, 1의 개수가 같다면 10진수를 기준으로 더 큰 값이 먼저 배치될 수 있도록 하는 문제이다.

내가 생각한 방법은 총 3개의 배열(리스트)을 필요로 한다.

1. 10진수를 담을 리스트 - 리스트1
2. 2진수로 변환된 문자열을 담을 리스트 - 리스트2
3. 각 2진수에 포함된 1의 개수를 담을 리스트 - 리스트3

위 3개의 리스트를 가지고 다음과 같은 순서로 문제를 해결한다.

1. 리스트1을 내림차순 정렬한다. (나중에 1의 개수가 같을 때, 큰 것이 먼저 배치될 수 있도록 하기 위함)
2. 리스트1의 순서와 동일한 순서로 리스트2에 변환된 2진수를 채운다.
3. 리스트3에 리스트2에 있는 2진수의 1의 개수를 순서대로 채운다.
4. 리스트3을 반복해서 돌면서, 해당 원소의 1의 개수가 num_of_ones라면 count를 늘린다.(리스트3을 다 돌았다면, num_of_ones를 1 줄이고 다시 반복한다.)
5. count가 k라면 현재 체크하던 인덱스에 위치한 리스트1 값을 출력하고 종료한다.

위 내용을 코드로 구현하면 아래와 같다.

n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 내림차순 정렬을 해야 1의 개수가 같을 때, 큰 것 먼저 출력 가능
arr.sort(reverse = True)

# 각각의 2진수를 담음
bin_arr = []
for element in arr:
	bin_arr.append(bin(element))

# 각 2진수에 포함된 1의 개수를 담음
ones_of_bin = [0 for i in range(n)]
for i in range(n):
	for j in range(2, len(bin_arr[i])):
		if bin_arr[i][j] == "1":
			ones_of_bin[i] += 1

# 1의 개수가 가장 많을 때부터해서, 2진수의 1의 개수가 num_of_ones개일 때 count를 늘려줌
# count가 k가 되면 그때의 10진수 출력 후 종료
count = 0
num_of_ones = max(ones_of_bin)
while count < k:
	for i in range(n):
		if ones_of_bin[i] == num_of_ones:
			count += 1
			if count == k:
				print(arr[i])
				break
	num_of_ones -= 1