수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109
logic
- 입력값 배열에 순위를 매겨주기
- 그러기 위해서는 중복을 제거해주기
- 시간복잡도를 줄이기 위해
- 중복 없는 배열의 값을 key로하고 값으로 순위를 매겨준 map 만들어주기
- map을 활용하면 숫자도 key로 쓸 수 있기 때문에!
- X의 값들을 dict의 key값으로 접근하여 value를 answer배열에 넣어주기
- answer를 한줄로 출력해주기
{
const n: string | null = prompt("숫자의 개수를 입력해주세요.");
const N: number = n ? parseInt(n) : 0;
if (N >= 1 && N <= 1000000) {
const numbers: string | null = prompt(
"숫자들을 빈칸을 사이에 두고 입력해주세요."
);
const nums: Array<number> = numbers
? numbers.split(" ").map((v) => parseInt(v))
: [];
if (nums.length === N) {
const dict = new Map();
const numsCopy: Array<number> = [];
nums.map((v) => (numsCopy.includes(v) ? numsCopy : numsCopy.push(v)));
numsCopy.sort();
numsCopy.map((item, idx) => dict.set(item, idx));
const ans : Array<number> = []
nums.map((v) => ans.push(dict.get(v)));
console.log(ans.join(" "))
} else {
console.log("입력한 숫자의 개수가 불일치합니다.");
}
} else {
console.log("숫자 N의 개수가 부적절합니다. (1 ≤ N ≤ 1,000,000)");
}
}
/**
* test1
*
* input
5
2 4 -10 4 -9
* output
2 3 0 3 1
*
* test2
6
1000 999 1000 999 1000 999
* output
1 0 1 0 1 0
*/