BOJ - 18870 좌표 압축

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

문제 등급: 실버2 

문제 아이디어 ; 정렬 후 딕셔너리를 사용해서 index를 순위로 표현 해준다. 

문제 풀이

 1) 좌표 압축 : 각 값을 크기 순위로 변형 하는 것이다. 문제 이해 부터 어려웠는데 결론적으로 각각 입력 받은 좌표값들이

전체 좌표값들 중에서 몇 번째로 큰 좌표인지를 입력받은 형태와 동일하게 출력 해준다. 

2) 입력 배열 

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);

let arr = input[1].split(" ").map(Number);

3) 중복 제거 및 오름차순 정렬  : 서로 다른  수라 했기 때문에 중복을 제거 해준다. (서로 다른 좌표)

let arrSet = [...new Set(arr)];
arrSet.sort((a,b)=>a-b);

4) Dictionary 사용 : let myMap = new Map();

let myMap = new Map();

5) 매핑 수행 : arrSet[i]을 i로 매핑해준다. 

for(let i=0;i<arrSet.length;i++){
    myMap.set(arrSet[i],i);
 }

6) 매핑된 값 가져오기 

answer="";
for(let x of arr){
    answer+=myMap.get(x)+" "
}
console.log(answer);

 

이해 자체가 어려웠던 문제였다. 또한 딕셔너리를 활용해 index로 매핑하는 법을 새로 배우게 되었다.

시간복잡도는 정렬 기능을 수행했기 때문에 O(NlogN)이다. 

 

전체 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let N = Number(input[0]);
// 입력 배열
let arr = input[1].split(" ").map(Number);
// 중복 제거 위한 집합 (서로 다른 수이기 때문)
let arrSet = [...new Set(arr)];
arrSet.sort(function(a,b){
    return a-b;
})
// dictionary 사용
let myMap = new Map();
// 매핑 수행
for(let i=0;i<arrSet.length;i++){
    myMap.set(arrSet[i],i);
}
// 매핑된 값 가져오기
answer="";
for(let x of arr){
    answer+=myMap.get(x)+" "
}
console.log(answer);