[백준/BOJ] 18870번 좌표 압축 (Javascript/ Node js)

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

18870번: 좌표 압축

문제 해석

문제는 간단하게 말하자면 각각 입력 받은 좌표값들이 전체 좌표값들 중에서 몇 번째로 큰 좌표인지를 입력받은 형태와 같은 자리, 형태로 출력해주면 된다는 것이다.

 

좌표값들 하나하나 마다 반복문을 사용해서 본인보다 작은 수 들을 세는 것은 시간복잡도를 계산해보지 않아도 시간초과가 날 것이라 생각했다.

 

해서, 생각해낸 방법

1. 입력받은 좌표 값들의 중복을 제거한다.

2. 좌표값을 내림차순으로 정렬한다.

3. 좌표값의 index를 사용해서 좌표값이 몇번째로 큰 수 인지 알아낼 수 있다.

var set = new Set([...arr]); //Set 객체를 사용해서 중복제거
var uniq = [...set];
var cnt = new Array(uniq.length);
cnt.fill(0);

uniq.sort(function(a, b){
    return b-a;
})

for(let i=0; i<cnt.length; i++){
    cnt[i] = uniq.length - i - 1;
}

4. 이제 cnt라는 배열에 uniq(중복제거, 정렬된 배열)의 원소마다 몇번째로 큰지를 uniq의 인덱스와 같은 순서대로 넣어주고,

 

var strArr = arr.join(" ");

for(let i = 0; i<uniq.length; i++){
    strArr = strArr.replaceAll(uniq[i], cnt[i]);
}

 

위와 같이 원본 배열(중복제거, 정렬되기 전 배열)의 좌표값들을 uniq 배열의 좌표값들로 검색해서 cnt 배열 안에 있는 숫자들로 전부 바꿔줄 생각이였다.

 

이렇게 풀고 제출해보자 메모리 초과가 발생했다. 아마도 replaceAll()을 사용할때 배열의 원소들을 검색하는 과정에서 발생한 것 같았다.

 

그래서 3번까지의 알고리즘은 놔두고, 배열 대신 Object를 사용해서 [Key - 좌표값 , Value - 몇번째로 큰지] 형태로 담는 방식으로 바꿨다.

 

전체코드

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim().split("\n");
input.shift();
var arr = input[0].split(" ").map(item => Number(item));

var uniq = [...new Set([...arr])];
var object = {};

uniq.sort(function(a, b){
    return b-a;
})

for(let i=0; i<uniq.length; i++){
    object[uniq[i]] = uniq.length - i - 1;
}

var str = "";

arr.forEach((item) => {
    str += object[item] + " ";
});
console.log(str);

 

Object, Array 시간복잡도 차이 관련 참고한 사이트-

https://velog.io/@jiwonyyy/javascipt-Set-vs-Array-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EB%B9%84%EA%B5%90-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94%EC%9D%B4%EB%9E%80

[javascipt] Set vs Array 시간복잡도 비교 (+ 해시테이블이란?)