[PCCP] 정렬 - 이진수 정렬 | 파이썬

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

정렬 - 이진수 정렬

앞서 공부한 [Python] 정렬 함수(sort, sorted)을 사용해 이진수 정렬 문제를 풀어보겠다.

---

문제

매개변수 nums에 숫자가 주어지면 nums의 원소들을 이진수로 변환했을 때 1의 개수가 적은 것부터 많은 것 순으로 정렬하여 반환하는 프로그램을 작성하세요.
만약 nums = [5, 6, 7, 8, 9]이고 이 원소들을 이진수로 변환하면 아래와 같다.

• 5 --> 101 : 1이 2개
• 6 --> 110 : 1이 2개
• 7 --> 111 : 1이 3개
• 8 --> 1000 : 1이 1개
• 9 --> 1001 : 1이 2개

이 수들을 이진수에서 1의 개수에 의해 오름차순 정렬하면 [8, 5, 6, 9, 7]이다.
위에 5, 6, 9는 이진수로 변환했을 때 1의 개수가 2개로 동일하면 십진수가 작은순(오름차순) 으로 정렬합니다.

---

입출력 예

n	k
[5, 6, 7, 8, 9]	[8, 5, 6, 9, 7]
[5, 4, 3, 2, 1]	[1, 2, 4, 3, 5]
[12, 5, 7, 23, 45, 21, 17]	[5, 12, 17, 7, 21, 23, 45]

---

제한사항

• nums의 길이는 1,000을 넘지 않습니다.
• 1 <= nums[i] <= 100,000

---

코드

def solution(nums):
    numsN = []
    answer = []

    for num in nums:
        # 이진수 변환 함수 사용
        numsN.append([num, int(str(format(num, 'b')).count('1'))])
        
    numsN.sort(key= lambda x : (x[1], x[0]))

    for i in range(len(nums)):
        answer.append(numsN[i][0])
            
    return answer
                  
print(solution([5, 6, 7, 8, 9]))
print(solution([5, 4, 3, 2, 1]))
print(solution([12, 5, 7, 23, 45, 21, 17]))

---

풀이

1. 먼저 num들을 format을 이용해 이진수로 변환시켜 1의 개수를 세 [num, 이진수의 1의 개수] 형태로 묶기
2. sort의 좌표 정렬을 이용해 저장되어 있는 num과 이진수의 1의 개수를 정렬
   • 이진수의 1의 개수가 적은 순으로 먼저 오름차순 정렬
   • 이진수의 1의 개수가 같다면 num을 기준으로 오름차순 정렬
3. 정렬된 nums를 return

만약 2진수의 1의 개수를 함수를 사용하지 않고 구하려면 코드는 아래와 같다.

for num in nums:
    tmp = num
    cnt = 0
    while tmp > 0:
        # 나머지는 0 아니면 1
        cnt += (tmp % 2)
        # 나눴으니 반 나누기
        tmp = tmp // 2
    numsN.append([num, cnt])