[백준18870-silver2] 좌표 압축 (javascript)

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

 

 

[풀이]

 

 

📌 좌표압축 ?

만약 x축의 좌표가 [0 ,1 ,2 ,3 ,100 ,150]과 같이 주어졌을 때, 0~3은 각 1씩 차이라 크게 문제 되지 않지만
100과 150을 탐색하기 위해서는 100까지, 150까지 탐색해야하는 문제점이 있다.
다시말해 4~99, 101~149는 쓰지 않는데 탐색하고 있는 시간낭비를 하고 있는 것이다.
숫자의 갭차이가 크게 늘어난다면 시간낭비는 더욱 늘어날 것이다.
이때 사용하는것이 좌표 압축이다.

 

좌표 압축 사용

0 ,1 ,2 ,3 ,100 ,150 을 0 ,1 ,2 ,3은 그대로 100을 4로 150을 5로 가정하고 비교한다면 매우 시간이 절약될 것이다.
그래서 0, 1, 2, 3, 100, 150 => 0, 1, 2, 3, 4, 5로 나타낼 수 있다.

 

구현 방법

먼저 값을 배열로 받고 중복되는 값은 필요 없으니 집합형태로 만들어 준다.
다음에 정렬을 통해 오름차순으로 만들고 각 값들의 인덱스를 좌표압축에 사용하면 된다

 

: 출처 : https://smhope.tistory.com/235

좌표압축

 

 

 

 

코드풀이 :

입력값의 중복 제거 -> 집합 사용 -> 배열로 만들어서 오름차순 정렬

객체를 선언하고 객체안에 key 와 value 를 넣어주었다

 

예를 들어

2번째 예제에서

6
1000 999 1000 999 1000 999

 

arr 는 [999,1000] 일 것이다 (= 집합으로 중복 제거 후 배열로 다시 오름차순 정렬)

 

arr[0] = 999 이므로 result[arr[i]] i; 를 한다면 객체에 {999:0} 가 입력되고 

최종 {999:0, 1000:1} 이 입력될 것이다.

 

 

 

let fs = require('fs');
let [n, ...input] = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); //.map(Number);

const tmp = input[0].split(' ').map(Number);

const setTmp = Array.from(new Set(tmp)).sort((a, b) => a - b);

const result = new Object();

setTmp.forEach((v, i) => {
  result[v] = i;
});

// console.log('Here!🌈', result); //{ '2': 2, '4': 3, '-10': 0, '-9': 1 }
let answer = '';
for (let val of tmp) {
  answer += result[val] + ' ';
}

console.log(answer);