[Python/알고리즘] 해시 Hash 완전정복(프로그래머스 - 전화번호 목록)

이번 차례는 역시나 코테에 자주 출제되는 해시 알고리즘이다.

 

코테 맞춤형 개념 설명

Hash는 key: value를 갖는 자료구조이다.

전화번호부와 같다. -> 검색창에 이름(key)를 입력하면, 결과(value)가 나온다.

이게 없다면, 반복문을 통해, 모든 전화번호를 확인해야함. -> 데이터가 많다면 정답이 될 수 없다.

HashMap을 만들면 빠르게 해결 가능!

* Hash는 모든 자료구조에 사용가능 *

 

기억해야할 함수: put, get, getOrDefualt

get(찾고자 하는 변수): 찾고자 하는 변수가 없으면 error

getOrDefault(찾고자 하는 변수, false): 찾고자 하는 변수가 없으면 false 반환

 

그럼, 언제 해시를 써야할까?

String을 기반으로 정보를 기록하고 관리해야할 때이다. 대부분  Key가 String 인 것이다.

예를 들자면,

1. 완주하지 못한 선수

선수 이름 -> 완주 여부 관리해야한다. 

String Key : bool Value로 관리하면 쉽게 풀 수 있다.

 

2.신고 결과 받기

게시판 사용자 중 신고 당한 사람을 기준으로 신고자 목록을 관리해야하는 문제이다.

신고당한 사람의 이름인 String이 기준이니까, 해시를 써야겠다고 생각해야한다.

String Key: ArrayList<String> Value로 사용하여 관리하면 된다.

 

3. 위장

옷의 종류에 따라 각각 몇개의 옵션이 있는지 세는 문제이다.

옷의 종류가 String이므로 String Key: Integer Value로 관리하는 해시 문제이다.

 

즉, String 을 기준으로 정보를 기록하고 관리하려면 단순배열으로 관리할 수 없으므로, Hash를 쓰자!

 

예제로 알아보기

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

문제 자세히 보기

프로그래머스

 

오답노트

처음에는 이중 for문으로 하나씩 체크하는 방식으로 구현했다. 예시 테스트케이스 3개에선 통과했지만, 채점시에 2개의 경우에서 시간초과가 떴다.. ㅜ

왜냐하면 문자열 비교를 String A in String B 로 했기 때문으로 보여서, startswith 함수를 사용해봤으나 1개의 경우에서 시간 초과가 떴다.

그래서 전화번호를 key로 관리하는 해시맵을 만들어 해결했다.

def solution(phone_book):
    ## 해시맵 생성: key - 전화번호부, value - 1
    hash_map = {}
    for num in phone_book:
        hash_map[num] = 1
        
    ## 접두어 찾기
    for num in phone_book:
        jubdoo = ''
        for n in num:
            jubdoo += n
            if jubdoo in hash_map and jubdoo!=num:
                return False
    
    return True

 

 

아직 해시맵이 낯설지만 더 열심히 연습해보자!