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

https://level.goorm.io/exam/195687/%EC%9D%B4%EC%A7%84%EC%88%98-%EC%A0%95%EB%A0%AC/quiz/1

구름LEVEL

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

ns = list(map(int, input().split()))
ns = sorted(ns, reverse=True)
ns_bin = []
ns_count = []

for i in ns:
    ns_bin.append(format(i, 'b'))
for i in ns_bin:
    ns_count.append(i.count('1'))

		
stack = []
for i in range(max(ns_count), 0, -1):
    for j in range(n):
        if ns_count[j] == i:
            stack.append(ns[j])
print(stack[k-1])

 

예시 1)

입력)

  8 6

  1 2 3 4 5 6 7 8

출력) 4

 

예시 2) 

입력)

  7 1

  1 2 4 8 16 32 64

출력) 64

 

 

구름에서 매일 코딩 문제를 1문제씩 풀이하는 구름톤 챌린지를 진행하고 있다.

벌써 5일차에 접어들었는데, 슬슬 문제가 어려워지기 시작해 블로그에도 기록을 남기고자 한다.

 

이 문제의 경우, 프롬프터로 숫자를 입력받고, 이를 두 가지 조건에 따라 정렬해야 한다.

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

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

 

조건에 따라

1) 먼저 모든 숫자를 내림차순으로 정렬한다.

2) 입력 받은 수를 이진수로 변환한다.

3) 이진수 표현식에서 1의 개수를 각각 세어 이를 리스트로 변환한다.

 

이제 10진수 숫자와 매칭되는 2진수 리스트가 2개 생성되었다. 이제 ns_count를 기준으로 가장 높은 값부터 1씩 감소시켜가며 원래 10진수 값을 스택에 차곡차곡 쌓아주기만 하면 된다.

 

단, k번째 값은 리스트 참조 시 k-1번 인덱스라는 점에 주의한다.

 

---

 

풀이 후 sorted 함수에 key로 조건을 줄 수 있다는 것을 추가적으로 알게 되었다.

이를 적용하면

ns_sorted = sorted(ns, key=lambda x: (bin(x).count('1'), x), reverse=True)
print(ns_sorted[k-1])

이렇게 단 두 줄로 위 로직을 구현할 수 있다.