해시 테이블(Hash Table)

 

 

 

앞으로를 위해서

4학년이 되면서 it기업을 목표를 잡고 코딩테스트를 공부하기로 마음먹게 되었습니다. 

 

 

프로그래머스의 고득점 kit을 처음으로 정리를 시작하면서 코딩 테스트를 리뷰하는 과정을 가지도록 하겠습니다.

참고 블로그 : davinci-ai.tistory.com/19

파이썬으로 구현하는 자료구조 요약 정리 - 해쉬 테이블(Hash Table)

 

 

그 첫번째는 해시 테이블입니다. 

우선 해시 구조란?

- key와 value로 이루어진 데이터 구조를 말합니다. key를 이용하여 찾으므로, 속도를 빠르게 만듭니다.

- 파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조입니다. 

- 배열로 미리 hash table 크기만큼 생성해서 사용, 시간이 빠르다는 장점이 있습니다.

- 검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우 주로 사용.

 

 

장점 

- 데이터의 저장, 검색 속도가 빠르다.

- 키에 대한 데이터가 있는지 (중복) 확인이 쉽다.

 

 

단점

- 일반적으로 저장공간이 많이 필요.

- 여러 키에 해당하는 주소가 동일한 경우 충돌을 해결하기 위한 별도 자료구조가 필요.

 

 

용어

1. 해시(Hash) : 임의 값을 고정 길이로 변환하는 것을 의미.

2. 해시 함수(Hash Function) : 특정 연산을 이용하여 키 값을 받아서 value를 가진 공간의 주소로 바꾸어주는 함수.

3. 해시 테이블(Hash Table) : 해시 구조를 사용하는 데이터 구조.

4. 해시 값(해시 주소, Hash Value or Address) : key값을 해시 함수에 넣어서 얻은 주소값 / 이 값을 통해 슬롯을 찾아간다.

5. 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간.

 

 

 

 

[프로그래머스] 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

 

 

나의 풀이

 

이름이 같은 사람이 2명이 참가 했을 때, 둘 중 한명만 완주 할 수 있다는 가정을 놓쳤던 것 같다. 그리고 효율성도 많이 떨어진다.

문자열이라 sort로 정리하고 단순히 포함되고 안되고로 해결하려 했던 것 같다.

 

 

다른사람의 풀이

1)

비슷한 아이디어라고 생각했다. 하지만 마무리를 잘하고 안하고의 문제 같습니다. 

 

 

2) collections을 활용

이렇게 짧게 collections.Counter를 사용해서 키 밸류값으로 나타내고 두개를 서로 빼서 키값으로 리턴한다는 아이디어가 대단하다고 생각했다.

 

 

 

 

[프로그래머스] 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

다른사람의 풀이

1)

해시 테이블에 대한 정의를 직관적으로 표현한 것 같다. hash값을 하나 만들고 pnum이 있으면 value값을 1로 주고 또 pnum안에 num이 존재하면 새로만든 temp값에 더해서 hash 테이블과 비교하여 pnum과 다르면 False를 반환하는 이해하기 쉬운 코드였다.