[JavaScript] 구름톤 챌린지 1주차 코딩테스트 : 이진수 정렬

📌  문제

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

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

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

📌  입력

첫째 줄에 주어지는 정수의 수 과 플레이어가 찾으려는 정수의 위치 가 공백을 두고 주어진다.
둘째 줄에 정수 a1, a2, ..., aN 이 공백을 두고 주어진다.

• 1 <= N =< 500,000
• 1 <= K <= N
• 1 <= ai <= 2^20

📌  출력

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

📌  예제 입출력

---

📌  풀이

알아야 하는 것

• toString

구할 것

• 입력 첫 줄에 주어지는 정수의 수를 num, 찾아야 할 정수의 위치를 target으로 둔다.
• 나머지 입력값 numbers는 공백을 기준으로 나눠 Number로 형변환 한 뒤, toString으로 2진수를 만든 후 split('')으로 쪼개준다.
• 그렇게 쪼갠 후 쪼갠 값이 1인 배열의 길이(1의 개수)를 binaryCounts라는 배열로 저장한다. 
• 정렬된 순서를 보존하면서 정렬하기 위해 numbers를 value, index를 기준으로 map 해서 배열 numbersWithCounts로 변환한다.
  • 이 때 value, 즉 numbers의 값들은 그대로 value로 저장하고 binaryCounts의 값도 저장하기 위해 index를 사용해 똑같이 저장해준다. 
  • 예시에서 numbers = [1, 2, 3, 4, 5, 6, 7, 8]이라면 아래와 같이 numbers의 값은 그대로 value에 저장하고, binaryCounts는 binaryCount라는 키값의 밸류값으로 하나씩 저장해주면 된다.

[

  { value: 1, binaryCount: 1 },

  { value: 2, binaryCount: 1 },

  { value: 3, binaryCount: 2 },

  { value: 4, binaryCount: 1 },

  { value: 5, binaryCount: 2 },

  { value: 6, binaryCount: 2 },

  { value: 7, binaryCount: 3 },

  { value: 8, binaryCount: 1 }

]

• numbersWithCounts를 정렬할 건데 binaryCount의 값이 같지 않다면, 즉 1의 개수가 같지 않다면 1의 개수를 기준으로 내림차순을 정렬해야 하기 때문에 b.binaryCount - a.binaryCount로 정렬해준다. binaryCount를 기준으로 내림차순 정렬하겠다는 뜻이다. 
• 만약 1의 개수가 같다면 원래 10진수를 기준으로 내림차순 정렬해야 하기 때문에 b.value - a.value로 정렬해주면 된다. 

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
	input.push(line);
	if (input.length === 2) {
		rl.close();
	}
});

rl.on('close', () => {
	let [num, target] = input.shift().split(" ").map(Number);
	let numbers = input[0].split(" ").map(Number);
	
	// 각 숫자를 2진수로 변환하고 1의 개수를 세어서 배열로 저장
	let binaryCounts = numbers.map((v) => v.toString(2).split('').filter((bit) => bit === '1').length);
	// 정렬된 순서를 보존하면서 정렬하기 위해 객체 배열로 변환
	let numbersWithCounts = numbers.map((value, index) => ({ value, binaryCount: binaryCounts[index] }));

	// 1의 개수를 기준으로 내림차순 정렬, 1의 개수가 같다면 원래 값에 대해 내림차순 정렬
	numbersWithCounts.sort((a, b) => {
		if (a.binaryCount !== b.binaryCount) {
			return b.binaryCount - a.binaryCount;
		} else {
			return b.value - a.value;
		}
	});

	let result = numbersWithCounts[target - 1].value;
	console.log(result);
});

1~2일차에 비해 확실히 체감 난이도가 높았던 문제

객체 배열로 변환하는 걸 바로 생각하지 못해서 약간 헤맸다 ㅎㅎ;