백준_좌표 압축_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을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• $-10^9$ ≤ $X_i$ ≤ $10^9$

예제 입력

5
2 4 -10 4 -9

예제 출력

2 3 0 3 1

Code

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

const N = +input[0]; // N개의 좌표
const coordinate = input[1]
  .split(' ')
  .map((x, idx) => ({ coordinate: +x, num: idx, cnt: 0 })); // 좌표 정보: {좌표, 순서번호, 좌표 압축}
coordinate.sort((a, b) => a.coordinate - b.coordinate); // 좌표 기준 오름차순 정렬

let count = 1;
for (let i = 1; i < N; i += 1) {
  // 앞 좌표와 동일하면 해당 cnt 적용
  if (coordinate[i].coordinate === coordinate[i - 1].coordinate)
    coordinate[i].cnt = coordinate[i - 1].cnt;
  // 같지 않다면 다음 count 적용
  else {
    coordinate[i].cnt = count;
    count += 1;
  }
}

// 다시 순서 번호 기준 오름차순 정렬 후 좌표 압축 결과 출력
console.log(
  coordinate
    .sort((a, b) => a.num - b.num)
    .map((coo) => coo.cnt)
    .join(' ')
);

풀이 및 해설

• 좌표 압축 결과 출력하기 ⇒ ${X_i}^*$(압축 결과) = $X_i$ > $X_j$를 만족하는 $X_j$의 개수
  

1. 좌표들을 입력받을 때 순서번호와 함께 배열에 저장
2. 좌표 기준으로 오름차순 정렬
3. 앞 인덱스랑 숫자가 같으면 앞 인덱스로 사용, 같지 않으면 번호 부여

시간 효율 개선하기

⇒ 중복 제거와 해시 Map 이용

1. 좌표 리스트 중복제거하여 배열로 만든 후 오름차순 정렬
2. 해시 Map 이용하여 [좌표값, 좌표압축 결과] 형태로 담기
3. 해시 Map에서 기존 좌표 리스트에 해당하는 값 출력

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

const N = +input[0]; // N개의 좌표
const coordinateX = input[1].split(' ').map(Number); // 좌표 정보 저장
const coordinatex = [...new Set(coordinateX)]; // 좌표 압축을 위한 중복 제거 배열
coordinatex.sort((a, b) => a - b); // 오름차순 정렬

const map = new Map();
coordinatex.forEach((x, idx) => map.set(x, idx)); // 좌표 압축 결과 해시 Map에 저장

let answer = '';
coordinateX.forEach((X) => (answer += map.get(X) + ' '));

console.log(answer);