코딩 테스트 공부 : 해시

개발자로서 더욱 성장하기 위해, 평소에 프로그래머스 사이트를 이용하여 코딩 테스트 풀이를 꾸준히 하고 있다. 처음에는 레벨 0, 1단계의 문제들을 풀다가 최근에는 코딩테스트 고득점 kit에 있는 유형별 풀이를 하나씩 해보고 있다. 오늘은 그 중에서 해시 유형의 문제에 대해서 공부한 내용을 남기고자 한다.

해시?

해시 테이블(또는 해시 맵)은 데이터를 key-value 쌍으로 저장하는 자료구조로, 1950년대에 등장했지만 아직도 많은 곳에서 유용하게 사용하고 있는 자료구조라고 한다.

해시 테이블은 key를 받아 임의의 해시 함수를 통해 도출된 해시 값을 배열의 Index로 사용한다. 이를 통해 O(1) 이라는 아주 빠른 속도로 데이터에 접근이 가능하다. 하지만, 데이터가 저장 시 적재되지 않는 빈 공간이 생겨 공간의 낭비로 이어지는 단점이 있다.

또한, 해시 함수는 해시값의 개수보다 ㄷ개 많은 키 값을 해시값으로 변환하기 때문에, 해시 함수가 서로 다른 두 개의 키에 대하여 동일한 해시값을 내는 해시 충돌이 발생하기도 한다. 그럼에도 불구하고, 해시 테이블을 많이 사용하는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있기 때문이다.

해시 method in JavaScript

ES6 이후 자바스크립트에서도 다른 프로그래밍 언어에 존재하는 해시 테이블의 종류인 Map, Set을 사용할 수 있게 되었다.

• Map : 자바스크립트의 객체에서 Key는 언제나 문자열만 가능하지만, Map은 Key에 함수, 숫자, 배열 같은 타입이 들어오는 것도 가능하며 order가 있다. 그렇기 때문에, map은 값이 삽입된 순서대로 순회를 한다.

new Map() // map을 만든다.
map.set(key, value) // key를 이용해 value를 저장한다.
map.get(key) // key에 해당하는 값을 반환. key가 존재하지 않으면 undefined 반환
map.has(key) // key가 존재하면 true, 존재하지 않으면 false 반환
map.delete(key) // key에 해당하는 값을 삭제
map.clear() // map 안의 모든 요소를 제거
map.size // 요소의 개수를 반환

let map = new Map();

map.set('1', 'str1')
map.set(1, 'num1')
map.set(true, 'bool1')

console.log(map.get(1)) // 'num'1
console.log(map.get('1')) // 'str1'
console.log(map.size) // 3

• Set : Set은 Map과 거의 유사하지만, 메모리 공간에 value는 저장하지 않고 key만 저장한다는 점이 다르다. Set은 중복을 허용하지 않는 값을 모아 놓은 컬렉션으로 생각하면 좋다.

new Set(iterable) // Set을 만든다. iterable 객체를 전달 받으면 그 안의 값을 복사해 set에 넣는다.
set.add(value) // 값을 추가하고, set 전체를 반환
set.delete(value) // 값을 제거하고, 호출 시점에 해당 값이 있으면 true, 없으면 false 반환
set.has(value) // 값이 존재하면 true, 없으면 false 반환
set.clear() // set을 비운다.
set.size // set에 몇 개의 값이 있는지 반환

let set = new Set();

let john = { name: "John" }
let pete = { name: "Pete" }
let mary = { name: "Mary" }

set.add(john)
set.add(pete)
set.add(mary)
set.add(john)
set.add(mary)

console.log(set.size) // 3

for(let user of set) {
	console.log(user.name) // John, Pete, Mary 순으로 출력
}

해시 코딩 테스트 공부 : 프로그래머스 <완주하지 못한 선수>

let participant = ["mislav", "stanko", "mislav", "ana"]	
let completion = ["stanko", "ana", "mislav"]

function solution(participant, completion) {
    
    let answer = '';
    
    const runnerMap = new Map()

    for( const start of participant){
      if(!runnerMap.get(start)){
        runnerMap.set(start, 1)
      } else {
        runnerMap.set(start, runnerMap.get(start)+1)
      }
    }

    for( const complete of completion){
      if(runnerMap.get(complete)){
        runnerMap.set(complete, runnerMap.get(complete)-1)
      }
    }

    for( const start of participant){
      if(runnerMap.get(start) >= 1){
        answer = start;
      }
    }
    return answer;
}

console.log(solution(participant, completion))