Key-value쌍으로 데이터를 빠르게 찾아보세요.
👩🏼💻 해시
- 키와 값이 한 쌍으로 구성된 데이터
👩🏼💻 해시 테이블
- key, value가 쌍을 이룬 형태로 데이터가 저장 되어있는 자료구조
- 데이터 검색과 저장이 아주 빠르게 진행됨
- 검색과 저장의 평균적인 시간복잡도가 O(1+α(적재율))에 수렴
👩🏼💻 해시 테이블의 원리
- 파이썬의 딕셔너리와 동일
[JS에서 해시 쓰는 방법]
- 사실 js에서 일반 배열에서 Key값에 문자열이 주는게 가능함
- 왜? js배열은 우리가 알고있는 배열과 조금 다른 희소배열이기 때문
- 희소배열 : 여러개의 자료형을 허락하는 배열
- 왜? js배열은 우리가 알고있는 배열과 조금 다른 희소배열이기 때문
🚨 Map
- key가 있는 데이터를 저장하는데 쓰이는 자료구조
- key값은 문자열 또한 가능
- new Map()
-> Map 객체를 만들때 쓰인다. - map.set(key,value)
-> key를 이용해 value값을 저장한다. - map.get(key)
-> key에 해당하는 value를 반환한다. - map.has(key)
-> key가 존재한다면 true, 없다면 false를 반환한다. - map.delete(key)
-> key에 해당하는 값을 삭제한다. - map.size
-> 요소의 개수를 반환한다.
[PROGRAMMERS] 완주하지 못한 선수들
[처음 시도한 코드]
원래 푸는 방식대로 편하게 풀었더니 정확성 테스트는 100점이었지만 효율성테스트에서 시간초과로 다 실패를 했다.
function solution(participant, completion) {
var answer = '';
for(let i = 0 ; i < completion.length ; i++) {
let idx = participant.indexOf(completion[i]);
participant.splice(idx, 1);
}
answer += participant[0]
return answer;
}
[다른 분들의 피드백]
- indexOf와 splice 사용을 줄여봐라
- indexOf는 원하는값을 찾기 위해서 순회를 진행합니다. 그러면 최악의 경우 completion의 마지막까지 순회를 하게 되는데, 값 하나를 순회하는데 1의 시간이 걸린다고 했을 때, 1부터 10만 까지의 합이 걸린다는 소리가 됩니다. indexOf에서만 50억이 넘는 시간이 걸리고, 밑에서 splice는 끝값을 제거하는것이기 때문에 시간이 소요된다고 해봤자 10만밖에 안될테고 그 밑은 shift는 가장 앞의 값을 제거 하기때문에 나머지 값들의 인덱스를 조정해야 해서 마찬가지로 순회를 진행합니다.
- 그러면 1부터 99999까지의 합으로 50억이 넘는 시간이 걸리게 됩니다. 이게 정확성 테스트에서 시간 초과를 발생시키는 시간인지는 모르겠지만, 효율성 테스트에서는 시간초과가 걸릴만큼의 시간이긴 합니다. 시간복잡도에 대한 이해가 없다보니까 직접해결하는것에 어려움이 있었던거 같군요.
- 간단한 팁을 드리자면 메소드를 사용했을 때 그 메소드가 인덱스를 가진 어떤 변수에서 값을 찾거나, 값을 제거하거나, 값을 추가할 때 그 과정이 어떨지 생각해 보세요. 주로 인덱스 부분에서 어떤 변화가 생길지 생각해 본다면 시간초과가 났을 때 그 이유를, 납득할만한 근거를 얻을 수 있을 겁니다.
- map, javascript에서는 dictionary인가요? 그것을 이용해서 값을 찾는데 걸리는 시간을 줄여 보세요.
- findIndex의 경우 최악의 경우 O(n)의 시간이 걸립니다. 해당 문제에서 배열의 길이가 100,000까지로 돼있는데 해당 코드는 최악의 경우 n2 즉 10,000,000,000이며 이 경우 시간초과가 발생합니다. 보통 길이가 100,000인 문제들은 O(nlogn)의 해결방법으로 푸셔야 시간초과가 발생하지 않습니다.
*정리* indexOf와 splice로 인해 시간 복잡도를 O(n2)으로 풀어서 시간 초과가 떴던 것이었다. 이를 O(nlogn)으로 줄여야했다.
(방안 1) sort함수를 이용하여 푼다.
이 경우, sort에서 nlogn, for문에서 n의 시간복잡도를 가지기 때문에 결론적으로 O(nlogn)으로 해결할 수 있었다.
function solution(participant, completion) {
var answer = '';
participant.sort();
completion.sort();
for(let i = 0; i < participant.length; i++) {
if(participant[i] !== completion[i]) {
answer += participant[i];
break;
}
}
return answer;
}
(방안2) 해시 이용
알고리즘 분류가 hash인 만큼 해시로의 풀이과정이 궁금했다.
이와 같이 풀면 O(n+m)의 복잡도를 갖게된다.
function solution(participant, completion) {
var answer = '';
const participantMap = new Map();
for (let i = 0; i < participant.length; i++) {
const name = participant[i];
participantMap.set(name, (participantMap.get(name) || 0) + 1);
}
for (let i = 0; i < completion.length; i++) {
const name = completion[i];
participantMap.set(name, participantMap.get(name) - 1);
}
participantMap.forEach((count, name) => {
if (count !== 0) {
answer = name;
}
});
return answer;
}
[PROGRAMMERS] 폰켓몬
function solution(nums) {
var answer = 0;
const typeMap = new Map();
let chooseNum = (nums.length)/2;
for(let i = 0 ; i < nums.length ; i++) {
const type = nums[i].toString();
typeMap.set(type, (typeMap.get(type) || 0 ) + 1);
}
{chooseNum >= typeMap.size ? answer = typeMap.size : answer = chooseNum}
return answer;
}
hash의 개념만 제대로 이해하면 map을 사용하는데 큰 어려움이 없을것 같다. 처음엔 헤맸지만 두번째 풀면서 hash에 대해 제대로 이해할 수 있었다.
'알고리즘' 카테고리의 다른 글
[알고리즘] 탐욕법(Greedy) (0) | 2024.02.06 |
---|---|
[알고리즘] 완전탐색 예제 # 1 단순 브루트포스 (0) | 2024.02.05 |
[알고리즘] 완전 탐색 (0) | 2024.02.02 |
[알고리즘] 브루트 포스(brute force) (0) | 2023.05.01 |
[BOJ] 2738 : 행렬 덧셈 (node.js) (0) | 2023.03.26 |