map.get(key) 대신, map.get(value) 만들기

필요성이 생긴 이유

오늘 자바스크립트 문제풀이를 하면서 다시금 Big O 의 중요성에대해서 느꼈다. 우선 오늘 문제풀이를 할 때 처음에는 Array를 통해서 접근하다가. Map으로 접근을 하였다. 우선 왜 Map을 사용하였는가? 라고 하기에 앞서 Array와 Object의 worst Big O를 비교하겠다

우선 Array Worst Big O

접근	O(1)
index 0에 삽입	O(n)
index 마지막에 삽입	O(1)
검색	O(n)
삭제	O(n)

Object Worst Big O

삽입	O(1)
제거	O(1)
탐색(value를 이용한)	O(n)
접근(key를 이용한)	O(1)

여기서 보면 value를 이용하여 탐색을 하면 시간이 O(n)만큼 걸리는 걸 볼 수 있다. 따라서, value로 접근하는 것을 줄여주는 방법이 필요하다! 

아 그리고 이건 혹시 나중에 Big O를 찾아볼 나를 위해 추가메모

Big O of Object Method

Object.keys()	O(n)
Object.values()	O(n)
Object.entries()	O(n)
Object.hasOwnProperty	O(1)

Array가 시간이 더 많이 걸리는 이유야 뭐.. Array에는 보이지 않는 key가 있다. 바로 index이다. 앞쪽에 삽입할 때 O(n)이 되는 이유는 index+1만큼 key를 모두 변경해야하기 때문이다.

 

해결책

---

const map = new Map()
const endMap = new Map()

맵을 두개를 활용하는 방법이다!

[[1,2], [2,3], [3,5]]라는 정렬이 있다고 하면

const arr = [[1,2], [2,3], [3,5]]
const map = new Map()
const endMap = new Map()
for(let i=0;i<arr.length;i++){
    map.set(arr[i][0], arr[i][1])
    endMap.set(arr[i][1], arr[i][0])
}

와 같이 만들면, endMap(valueOfMap) 와 같이 map 에서의 value를 입력하면 key를 O(1)로 찾아낼 수 있다! 여기서 한가지 주의를 한다면, endMap에 set되어야할 것은 고유하지 않는다면 업데이트가 되서 값이 없어지기에, 고유하지 않는 key가 들어간다면 Object를 이용하여 삽입을 하는 것과 같이 약간의 추가적인 수정을 할 필요는 없어보인다.