[JavaScript/코딩테스트] <백준 - 18870번 좌표 압축>

문제

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

 

🔗분류

값 / 좌표 압축, 정렬

 

🔗문제 설명

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

🔗입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

🔗출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

---

풀이

 

좌표 압축이란 주어진 수나 좌표의 범위를 줄여서 더 작은 정수로 변환하는 것이다

여기 문제에서는 자기보다 작은 수의 개수를 세면 되는 문제이다

여기서 주의할 점은 중복되는 수가 있을 시 중복으로 세지 않고 한 번만 세야 한다는 점❗❗

 

---

 

시간 초과

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

let N = Number(input[0]);
let M = input[1].split(' ').map(Number);
let new_M = [...new Set(M)];

let result = [];
for (let i = 0; i < N; i++) {
  let cnt = 0;
  for (let j = 0; j < new_M.length; j++) {
    if (M[i] > new_M[j]) {
      cnt++;
    }
  }
  result.push(cnt);
}

console.log(result.join(' '));

 

시간 초과가 나왔던 내 첫 정답이다

for문을 이용하여 XN과 중복된 수를 제거한 XN을 비교하여 문제를 풀었다.

 

하지만 시간 초과가 나와서 서치를 해보니 

for 문은 정해진 횟수만큼 반복하므로 시간 복잡도가 O(n)이 나온다고 한다

즉 나는 for문을 2번 사용했으므로 O(n) ×O(n)=O(n2)의 시간복잡도를 가지게 되었다...

 

최종 정답

 

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

let N = Number(input[0]);
let num = input[1].split(' ').map(Number); 
let result = {};

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

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

let print = '';

for (let v of num) {
  print += result[v] + ' ';
}

console.log(print.trim());

 

기존 for문에서 객체를 사용해서 문제를 풀어 시간 복잡도를 낮 쳐서 문제를 풀 수 있었다

객체는 메모리에 더 많은 데이터를 저장할 수 있는 구조라서 데이터에 빠르게 접근이 가능해

평균 O(1)의 시간 복잡도를 가진다고 한다. 

 

 

후기

 

 

사실 지금까지는 알고리즘을 잘 알지 못해서 풀 수 있는 문제들이 많았다

하지만 문제를 풀수록 알고리즘을 요구하는 문제들이 많아지고 알고리즘을 알지 못하면 문제를 풀 수 없었다 ㅜㅜ

알고리즘 공부를 개을리 하지 않고 꾸준히 공부하며 실력을 키워나가야겠다.