해시(Hash)
Hash, Python, 프로그래머스
알고리즘을 정리하고,
프로그래머스의 문제를 바탕으로 활용해보는 연재.
Hash란?
- 키(Key)-데이터(Value) 쌍을 저장하는 데이터 구조
- Key를 통해 바로 데이터를 받아올 수 있으므로, 검색 속도가 빨라짐
- 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
- 관련 자료 구조 : 딕셔너리(Dictionary)
문제 예시
1. 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 단, 참가자 중에는 동명이인이 있을 수 있습니다.
title: 프로그래머스 - 완주하지 못한 선수
score: 정확성 50 / 효율성 50 / 합계 100.0
worst result: 정확성 0.82ms / 효율성 69.42ms
def solution(participant, completion):
dic = {}
# participant list
for person in participant:
if person in dic.keys():
dic[person] += 1
else:
dic[person] = 1
# contradict from completion
for person in completion:
if person in dic.keys():
dic[person] -= 1
# find person remained
return next((k for k,v in dic.items() if v == 1), None)
next(반복가능한 객체, 기본값): 반복할 때는 해당 값을 출력하고, 반복이 끝났을 때는 기본값을 출력
2. 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
ex) [“119”, “97674223”, “1195524421”]
3. 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
EX)[[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]]
4. 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다.
plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
장르 종류는 100개 미만입니다.
장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
모든 장르는 재생된 횟수가 다릅니다.