백준 | 18870번 좌표 압축 (JavaScript 풀이)

문제 소개

백준 18870번 "좌표 압축"은 정렬과 해시맵을 활용하는 대표적인 문제입니다.

문제 요약

• 수직선 위의 N개 좌표를 압축하는 문제
• 각 좌표를 "자신보다 작은 서로 다른 좌표의 개수"로 변환
• 예: [2, 4, -10, 4, -9] → [2, 3, 0, 3, 1]

---

핵심 개념: 좌표 압축이란?

좌표 압축 = 순위 매기기! 

좌표 압축은 큰 범위의 좌표들을 작은 범위로 압축하는 기법입니다.

원본 좌표: -10억 ~ 10억 범위
압축 후: 0 ~ N-1 범위

실생활 비유

학교에서 시험 점수로 등수를 매기는 것과 같습니다!

• 45점 → 3등 (0부터 시작하면 2)
• 97점 → 1등 (0부터 시작하면 0)
• 73점 → 2등 (0부터 시작하면 1)

---

🔍 문제 접근 방법

Step by Step 풀이 과정

1️⃣ 중복 제거 & 정렬

javascript

// 원본: [2, 4, -10, 4, -9]
// Set으로 중복 제거: [2, 4, -10, -9]
// 정렬: [-10, -9, 2, 4]

2️⃣ 압축값 매핑

javascript

// 작은 수부터 0, 1, 2, 3... 부여
-10 → 0
-9  → 1
2   → 2
4   → 3

3️⃣ 원본 배열 변환

javascript

// 각 원본값을 압축값으로 변환
[2, 4, -10, 4, -9]
[2→2, 4→3, -10→0, 4→3, -9→1]
[2, 3, 0, 3, 1] ✅

---

💻 전체 코드 구현

방법 1: Map과 forEach 활용

javascript

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

const N = parseInt(input[0]);
const coords = input[1].split(" ").map(Number);

// 1단계: 중복 제거하고 정렬
const uniqueSorted = [...new Set(coords)].sort((a, b) => a - b);

// 2단계: Map으로 압축값 저장
const compressMap = new Map();
uniqueSorted.forEach((value, index) => {
    compressMap.set(value, index);
});

// 3단계: 원본 배열 변환
const result = coords.map(coord => compressMap.get(coord));

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

---

방법 2: 객체와 for문 활용

javascript

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

const N = parseInt(input[0]);
const coords = input[1].split(" ").map(Number);

// 1단계: 중복 제거하고 정렬
const uniqueSorted = [...new Set(coords)].sort((a, b) => a - b);

// 2단계: 객체로 압축값 저장
const compressMap = {};
for (let i = 0; i < uniqueSorted.length; i++) {
    compressMap[uniqueSorted[i]] = i;
}

// 3단계: 원본 배열 변환
const result = [];
for (let i = 0; i < N; i++) {
    result.push(compressMap[coords[i]]);
}

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

---

시각적 이해

예제 1 동작 과정

원본 배열:     [2, 4, -10, 4, -9]
      ↓ 중복 제거 & 정렬
정렬된 배열:   [-10, -9, 2, 4]
      ↓ 인덱스 부여
압축 매핑:     {-10:0, -9:1, 2:2, 4:3}
      ↓ 원본에 적용
결과:         [2, 3, 0, 3, 1]

예제 2 동작 과정

원본 배열:     [1000, 999, 1000, 999, 1000, 999]
      ↓ 중복 제거 & 정렬
정렬된 배열:   [999, 1000]
      ↓ 인덱스 부여
압축 매핑:     {999:0, 1000:1}
      ↓ 원본에 적용
결과:         [1, 0, 1, 0, 1, 0]

---

시간복잡도 분석

단계	연산	시간 복잡도
중복 제거	Set 생성	O(N)
정렬	sort()	O(N log N)
매핑 생성	forEach/for	O(N)
변환	map/for	O(N)
전체		O(N log N)

---

⚠️ 주의사항 & 팁

1. 정렬 시 비교 함수 필수!

javascript

// ❌ 잘못된 방법 (문자열 정렬)
arr.sort()  // ['-10', '-9', '2', '4']

// ✅ 올바른 방법 (숫자 정렬)
arr.sort((a, b) => a - b)  // [-10, -9, 2, 4]

---

2. Map vs 객체 선택

javascript

// Map 사용 - 더 명확한 의도
const map = new Map();
map.set(key, value);
map.get(key);

// 객체 사용 - 더 간단한 문법
const obj = {};
obj[key] = value;
obj[key];

---

3. 중복 제거는 Set이 최고!

javascript

// Set으로 간단하게
const unique = [...new Set(array)];

// filter로 하면 복잡 (비추천)
const unique = array.filter((v, i) => array.indexOf(v) === i);

---

정리

좌표 압축은 정렬 + 해시맵의 조합으로 해결하는 전형적인 패턴입니다.

핵심 요약:

1. Set으로 중복 제거
2. 정렬로 순서 정하기
3. Map/객체로 빠른 검색
4. 원본 배열 변환

**시간복잡도 O(N log N)**으로 백만 개의 데이터도 효율적으로 처리할 수 있습니다.