반응형 해시4 [기술면접] 해시테이블 파이썬 구현 해시테이블이란? 딕셔너리 자료형을 생각하면 된다. 딕셔너리 자료형은 key값을 통해 value값을 O(1)속도로 찾는다. 여기서 key값을 특정한 hash값으로 변경해준 뒤 이 hash값으로 value를 찾는데 이러한 hash값을 모아논 자료형이 해시테이블이다 즉 해시테이블은 세가지만 기억하자 key hashkey (그림에서 buckets) value 해시테이블의 과정은 이렇다. 1. key값을 기준으로 hashkey를 계산한다. 2. hashkey를 기준으로 value를 찾는다. 아래는 파이썬으로 기본적인 hashtable을 구현해본 것이다. class hashTable: def __init__(self, tableSize): self.tableSize = tableSize self.hashTable .. 2021. 4. 12. [프로그래머스][해시] 위장 programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 이걸 해시라고 해야하는게 맞는건지... 그냥 순열 문제이다. 모자가 3개, 옷이 5개, 신발이 4개 있다 치자 모자를 고르는 경우의수는 3+1 = 4 (+1은 선택하지 않음을 의미) 옷을 고르는 경우의수는 5+1 = 6 신발을 고르는 경우의수는 4+1 = 5 문제에서 아예 안고르는 경우의 수는 빼라 했으므로 마지막에 -1 해주면 된다. 4 * 6 * 5 - 1 이런식으로 풀면된다. def solution(clothes): answer = 0 mydict = {} for i in clothes: if i[1] in mydict: mydict[i[1]] = mydi.. 2021. 3. 17. [프로그래머스][해시] 전화번호 목록 programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제는 풀었는데 다른사람이 파이썬 내장함수로 한줄로 푸는거 보고 충격... 정리 따로 해야겠다. 아이디어는 이렇다. 전화번호부로 set을 이용해 hash테이블을 만든다. 각번호를 순회하면서 이중포문을 통하여 번호의 부분문자열을 얻은뒤 hash 테이블에 있는지 확인한다. hashtable에 있다면 누군가의 접두어가 된다는 뜻이므로 False를 리턴한다 이렇게 하면 시간복잡도.. 2021. 3. 12. [프로그래머스][해시] 완주하지 못한 선수 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr c++스타일로 풀어봤다. completion 배열을 dictionary로 만들어준다. value값을 기본적으로 1로 주고 동명이인이 있는경우 value에 1을 더해주어 몇명이 있는지 세어준다. 이후 participant를 확인하면서 이름이 존재 할 때 마다 value값을 -1씩 해준다. value가 0이거나 dictionary에 없는경우가 답이므로 해당값 .. 2021. 3. 12. 이전 1 다음 반응형
