좌표 압축

문제

백준 18870번 - 좌표 압축

언어

JavaScript

순서도

입력받은 배열을 복사해서 오름차순으로 정렬
Map 을 이용해서 각 숫자마다 자신보다 작은 수가 몇 개 존재하는지 세기 (중복 없이)
Map 을 이용해서 기존의 배열에서 각 숫자마다 자신보다 작은 수가 몇 개 존재하는 지 출력

문제 풀이 step 1

N 개의 좌표가 주어지는 데, 이 좌표에 좌표 압축을 적용하려 합니다.
문제를 요약하면, 각 숫자마다 자신보다 작은 숫자가 중복 없이 몇 개 있는지 알아내는 문제입니다.

문제 풀이 step 2

우선, 주어진 수열과 똑같은 배열을 하나 생성합니다. 그리고 오름차순으로 정렬합니다.
그리고 Map 을 이용해서 각 숫자마다 중복 없이 자신보다 작은 숫자의 개수를 저장합니다.
그리고 위 과정을 통해 생성된 Map 을 이용해서, 아까 주어진 수열의 각 숫자 마다 자신보다 작은 숫자의 개수 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

Set 으로 각 숫자의 중복을 제거한 후, 이를 배열로 만들어서 오름차순으로 정렬하고, 나머지 로직을 이어가려 했지만, 시간 초과가 발생했습니다.
대신 Set 을 이용하지 않고, 배열을 오름차순으로 정렬하고, 중복될 경우 count 를 증가시키지 않고, 중복될 경우에만 count 를 증가시키는 방식으로 중복을 제거할 수 있었습니다.
간단한 방법이지만, 시간을 상당히 줄일 수 있는 좋은 방법이라고 생각합니다.
앞으로 다뤄볼 기법 : UpperBound, LowerBound 알고리즘

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);

	// 복사 후 오름차순 정렬
	const sorted = [...arr].sort((a, b) => a - b);

	// Map 을 이용해서 중복 없이 각 숫자마다 자신보다 작은 숫자가 몇 개 있는지 세기
	let cnt = 0;
	const orderMap = new Map();
	for (let i = 0; i < sorted.length; i++) {
		if (orderMap[sorted[i]] !== undefined) continue;

		orderMap[sorted[i]] = cnt++;
	}

	// 위에서 구한 Map 을 이용해서 기존의 수열에서 각 숫자마다 자신보다 작은 숫자가 몇 개 있는지 찾기
	const res = [];
	for (let i = 0; i < n; i++) {
		res[i] = orderMap[arr[i]];
	}

	// 문자열 형태로 변환 후 출력
	return res.join(" ");
};

console.log(solution(input));