구름톤 챌린지 1주차-5일차(이진수 정렬)

https://9oormthonchallenge.oopy.io/

문제

접근

• 주어진 수열에 각 수들을 2진수로 나타냈을 때, 2진수에 포함된 1의 개수를 추가해서 정렬하면 될 것 같다.

구현

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
	const int *first = (const int *)a;
	const int *second = (const int *)b;
	if (first[1] < second[1])
		return 1;
	else if (first[1] > second[1])
		return -1;
	else if (first[0] < second[0])
		return 1;
	else if (first[0] > second[0])
		return -1;
	else
		return 0;
}

int n, k, arr[1111111];

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		arr[i * 2] = a;
		int count = 0;
		while (a) {
			a &= (a - 1);
			count++;
		}
		arr[i * 2 + 1] = count;
	}
	qsort(arr, n, sizeof(int) * 2, compare);
	printf("%d\n", arr[(k - 1) * 2]);
	return 0;
}

• 수열을 입력받으며 arr[i * 2]엔 입력받은 수를, 입력받은 수를 2진수로 나타냈을 때 1의 개수를 arr[i * 2 + 1]에 저장한다. 한 수가 int 2개의 크기를 갖는다.
• qsort(시작 메모리 주소, 자료의 개수, 자료의 크기, 자료 비교 함수)를 실행한다.
• 자료 비교 함수 compare는 어떤 자료가 먼저와야 하는지 반환하는 함수이다. 2진수로 나타냈을 때 1의 개수가 작을수록, 같다면 크기가 작을수록 뒤로 가야 한다.
• k번째 수를 출력한다.

2진수로 나타냈을 때 1의 개수를 구하는 법은 이번에 새로 알게 되었다.

int a = 7
int count = 0;
while (a) {
    if (a & 1) count++;
    a >>= 1;
}

원래 이렇게 작성했는데, 더 빠른 방법이 있었다.

int a = 7
int count = 0;
while (a) {
    a &= (a - 1);
    count++;
}

이렇게 하면, a &= (a - 1)를 실행할 때, 1의 개수가 하나씩 줄어든다. 즉 while loop를 count만큼만 돌고 나와서 1의 개수를 구할 때 더 빠르다.