[ 백준 18870 ] JavaScript 풀이 ( 표준 내장 객체 Map )

📌 문제

백준 18870 : 좌표 압축

문제를 간단히 설명하면
입력받은 N개의 수를 좌표 위에 나열하고 각 입력받은 수보다 낮은 좌표계에 존재하는 수의 갯수를 하나씩 출력하는 문제다.
(ex. 첫 번째 입력 값인 2보다 낮은 좌표에 존재하는 값은 (-9, -10) 2개로 2를 출력한다.)

📌 문제 접근 방법

처음 문제를 접근 했을 땐 원본 배열을 유지하고 새로운 배열에 sort() 메서드로 오름차순 정렬한 뒤 indexOf()로 원본 배열과 비교하여 index를 출력하려고 했다.

하지만 결과는 시간 초과가 나왔고, 이유는 마지막 for of 문에서 indexOf()가 원본 배열의 전체를 최대로 탐색하여 결과적으로 O(N^2)의 시간 복잡도가 나오기 때문이라고 생각한다.

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

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

//새로운 배열에서 중복을 제거하고 오름차순 정렬
let newArr = [...new Set(arr)]
newArr = newArr.sort((a,b) => a-b)

let answer = ""

// indexOf를 활용하여 입력 받은 값의 index를 출력
for(x of arr){
  answer += newArr.indexOf(x) + " "
}

console.log(answer)

그래서 문제 풀이 강의를 참고하였고, 강의에서 표준 내장 객체 Map을 사용하여 이번에 문제와 함께 정리해 Map을 이해해보려고 한다.

📌 Map을 활용한 문제 풀이

표준 내장 객체 Map이란?

Map 객체는 키-값 쌍과 키의 원래 삽입 순서를 기억한다. 모든 값(객체 및 원시 값 모두)은 키 또는 값으로 사용될 수 있다.

set() 메서드로 값을 삽입하고, delete() 메서드로 값을 삭제하고, get() 메서드로 값을 출력한다.

const map1 = new Map();

map1.set('a', 1);
map1.set('b', 2);
map1.set('c', 3);

console.log(map1.get('a'));
// Expected output: 1

map1.set('a', 97);

console.log(map1.get('a'));
// Expected output: 97

console.log(map1.size);
// Expected output: 3

map1.delete('b');

console.log(map1.size);
// Expected output: 2

console.log(map1)
// Expected output : Map(2) { 'a' => 97, 'c' => 3 }

문제 풀이

indexOf 대신 Map 객체에 담긴 키 값을 바탕으로 get() 메서드를 활용해 index 값인 값을 출력한다는 차이가 있다.

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

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

// 새로운 배열에서 중복을 제거하고 오름차순 정렬
let newArr = [...new Set(arr)]
newArr = newArr.sort((a,b) => a-b)

// Map 객체를 생성하고 오름차순 정렬된 배열의 값과 index를 삽입
let myMap = new Map();
for (let i = 0; i < newArr.length; i++) {
  myMap.set(newArr[i], i);
}

let answer = "";

// 원본 배열의 값들을 myMap 객체에서 탑색하여 출력
for (x of arr) answer += myMap.get(x) + " ";
console.log(answer);

코드를 작성해보고 해석해보았을 때 indexOf()로 배열을 탐색하는 거랑 큰 차이가 없는 것 같이 느껴져 Map 객체의 get() 메서드의 원리를 알아보았다.

📌 왜 Map이 시간 복잡도가 더 낮을까?

기본적으로 배열과 Map 객체의 데이터 저장과 검색 방식에 차이가 있다.

배열은 값들이 연속된 메모리 공간에 저장되어 있다. indexOf() 메서드를 사용하면 연속된 메모리 공간을 하나씩 탐색하며 해당 원소의 인덱스를 알아낸다. 그래서 시간 복잡도가 최대 O(N)까지 나올 수 있는 것이다.

반면 Map 객체의 경우 해시 테이블 자료구조로 데이터를 관리한다.
해시 테이블이란 데이터의 특정 값을 키(key)로 매핑하여 값을 저장하고 검색하는 데 사용된다. 해시 테이블은 키-값 쌍을 저장하는데, 이를 해시 함수를 통해 고유한 해시 코드로 변환하여 내부적으로 저장한다.

그래서 get 메서드로 키를 검색할 때 아래 그림처럼 해시 함수로 값의 메모리 위치를 얻어 특정 메모리를 바로 참조하여 객체의 전체를 하나씩 참조하는 것이 아니라 최대 O(1)의 시간 복잡도를 만들 수 있다.

여기서 최대 O(1)이라고 말하는 이유는 해당 위치에 값이 존재하지 않거나 해시 충돌이 발생할 경우 최대 O(N)의 복잡도가 될 수도 있기 때문이다. 이를 해결하는 방법으로 체이닝과 개방 주소법이 있다고 하는데 나중에 알아보기로 하자..

📌 마무리

결론적으로 indexOf() 메서드와 Map 객체의 get() 메서드는 동작 방식과 자료구조에 큰 차이가 있기 때문에 Map 객체를 사용했을 때 낮은 시간 복잡도로 문제를 해결할 수 있었던 것이다. 그리고 자바스크립트의 객체 역시 해시 테이블 자료구조를 사용한다고 하여 일반 객체로도 구현할 수 있을 것 같다.