83. 18870 (좌표압축)

let input = require('fs').readFileSync(0).toString().trim().split("\n");

let N = parseInt(input[0]);
let tmp = input[1].split(" ").map(Number);
result = new Object();
resultPrint = "";

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

for(let i = 0 ; i<arr.length;i++){
  result[arr[i]]=i;
}

for(let val of tmp){
  resultPrint += result[val] + " ";
}

console.log(resultPrint)

문제 요약

x좌표가 들어왔을 때 효율적으로 탐색할 수 있게 좌표압축을 구현해라

설명

좌표압축의 개념은 아래에 들어가보자.

https://smhope.tistory.com/235

좌표압축

indexOf를 사용해 문제를 풀 수도 있지만 시간초과가 발생할 것이다.

따라서 객체를 사용해주었다.

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

 입력값의 중복을 제거하기 위해 집합을 사용하고 그것을 배열로 만들고 오름차순으로 정리해주었다.

 

result = new Object();

for(let i = 0 ; i<arr.length;i++){
  result[arr[i]]=i;
}

다음과 같이 객체를 선언하고 객체안에 key 와 value를 넣어 주었다.

 

예를 들어 

6
1000 999 1000 999 1000 999

가 들어 온다면

arr는 [999,1000] 일 것이다.

 

arr[0] = 999 이므로 result[arr[i]]=i;를 한다면 객체에 {999:0}가 입력되고 최종 {999:0 , 1000:1}이 입력될 것이다.

for(let val of tmp){
  resultPrint += result[val] + " ";
}

console.log(resultPrint)

객체에 값을 불러내고 공백과 함께 문자열로 만들어 출력해주었다.