해시

해시(해시 테이블)이란 Key-Value를 맵핑하여 데이터를 저장하는 자료구조. 파이썬에서는 기본 제공되는 dict 딕셔너리 자료형을 사용하면 된다.

원소의 개수를 셀 때 해시와 collections 모듈의 Counter 클래스를 사용하면 좋다.

딕셔너리와 리스트의 시간 복잡도 차이

Operation	Dictionary	List
Get	O(1)	O(1)
Insert	O(1)	O(1) ~ O(N)
Update	O(1)	O(1)
Delete	O(1)	O(1) ~ O(N)
Search	O(1)	O(N)

원소를 넣거나 삭제, 찾는 일이 많을 때에는 딕셔너리를 사용하는 것이 좋다

딕셔너리 사용하기

딕셔너리 생성

dict1 = {} # {}
dict2 = dict() # {}

get

• [] 사용하기
• get 메소드 이용하기
  get 메소드는 get(key,x) 로 사용. (두번째 인자는 만약 딕셔너리에 key가 없는 경우, x를 리턴하도록 설정하는 것)

set

• [] 사용하기

delete

• del dict_obj[key]
  만약 딕셔너리에 key가 없다면 keyError가 발생

• pop(key[,default])
  key 값에 해당하는 value를 리턴. key가 없다면 두번째 파라미터인 default를 리턴.
  (만약 default 설정하지 않았을 시엔 keyError가 발생)

순회 (iterate)

• key로만 순회하기
  for key in dictionary:
• key, value 동시 순회하기 (items() 사용)
  for key, value in dictionary.items():

기타 메소드

• 특정 key가 딕셔너리에 있는지 조회할 때 : in
• key만 뽑아낼 때 : keys()
• value만 뽑아낼 때 : values()

딕셔너리 정렬

• key 기준으로 정렬
  sorted(dictionary.items()) : 오름차순 정렬, 정렬된 딕셔너리를 리스트 형으로 반환
  • dictionary.keys() 로 정렬 : 정렬된 Key 값만 리스트로 반환
  • dictionary.items()로 정렬 : 튜플(Tuple) 형태로 Key값 기준으로 정렬된 리스트가 반환
• value 기준으로 정렬하기
  sorted 함수에 key 옵션을 lambda 함수를 이용하여 value값으로 지정
  sorted(dictionary.items(), key=lambda item : item[1])
  (item[0] : key, item[1] : value)

---

프로그래머스 고득점 kit 문제

Lv 1. 폰켓몬

딕셔너리에 폰켓몬 이름을 기준으로 값을 넣어준다. 딕셔너리의 key값의 개수가 폰켓몬의 총 종류 수이므로 n/2와 key값 길이를 비교하여 더 작은 값을 리턴하면 된다.

def solution(nums):
    answer = 0
    d = {}
    for item in nums:
        if item in d:
            d[item] += 1
        else:
            d[item] = 1
    
    if len(d.keys()) > (len(nums) / 2):
        answer = len(nums) / 2
    else:
        answer = len(d.keys())
    return answer

Lv 1. 완주하지 못한 선수

dict.fromkeys(key값, value) 메서드 : key값으로 지정할 리스트를 넘겨준 뒤 value로 지정할 값을 넘겨주면 딕셔너리를 생성하여 반환
참가자 이름을 기준으로 딕셔너리에 값을 넣어준다. 완주자 배열을 돌면서 딕셔너리에서 값을 빼주는데 (시간복잡도 O(1)) 만약 값이 0이면 해당 키 값을 없애준다.
완주자와 참가자는 1명 차이가 나므로 최종적으로 딕셔너리에 남아있는 키 값이 완주하지 못한 선수의 이름이다.

def solution(participant, completion):
    answer = ''
    
    d = dict.fromkeys(participant, 0)
    
    for p in participant:
        d[p] += 1
    
    for c in completion:
        d[c] -= 1
        if d[c] == 0:
            del d[c]
    
    for i in d.keys():
        answer = i
    return answer

Lv 2. 전화번호 목록

엄청나게 삽질했던 문제. 이틀을 붙잡았다... 그리고 전화번호가 0~9 사이의 숫자로 시작할 수 있음을 잊고 풀어서 테케에서도 우수수 틀렸다.

1. 딕셔너리에 싹 넣고 리스트 슬라이싱을 통해 비교 : 당연히 시간초과
2. 딕셔너리에 0 ~ 9 사이의 키 값을 기준으로 데이터를 넣고 리스트 슬라이싱을 통해 비교 : 시간 초과 (효율성 3,4번)
3. 2번 풀이에 길이순 정렬을 위해 sort() 추가 : 시간 초과 (효율성 3,4번)

# 3. 효율성 3,4번 테케에서 시간초과 난 코드 (이렇게 풀면 안된다...)
def solution(phone_book):
    answer = True
    d = { str(i):[] for i in range(10) }
    phone_book.sort()
    for phone in phone_book:
        if len(d[phone[0]]) == 0:
            d[phone[0]].append(phone)
        else:
            for item in d[phone[0]]:
                for i in range(min(len(item), len(phone))):
                    if item[i] != phone[i]:
                        break
                    if i == (min(len(item), len(phone)) - 1):
                        return False
            d[phone[0]].append(phone)
    return answer

4. (정답) sort()를 해주고 나면 굳이 다 살펴볼 필요가 없음을 캐치해야 한다!!!!

   ['1', '11', '112', '345']

   데이터를 정렬한 뒤에는 이렇게 생겼을 것이다. 그러면 접두사가 될 수 있는 요소는 바로 이전에 등장한 데이터이다. 굳이 다 살펴볼 필요가 없는 것!!

# 정답 코드
def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
    return answer

Lv 2. 의상

1. 조합을 사용해서 풀이 -> 테케 1번만 시간초과 (아마도 n=30인듯)

# 시간초과난 코드
import math
from itertools import combinations
def solution(clothes):
    answer = 0
    # 조합으로 뽑아내면 될 듯
    data = {}
    for item in clothes:
        name, kind = item
        if kind in data:
            data[kind] += 1
        else:
            data[kind] = 1
    
    case = []
    for i in range(1, len(data.keys())+1):
        case += list(combinations(list(data.keys()), i))
    
    for item in case:
        result = 1
        for i in range(len(item)):
            result *= (math.comb(data[item[i]], 1))
        answer += result
    
    return answer

2. 한개씩 경우를 곱해가면서 데이터를 추가하는 방식... 시간초과 ㅠ

# 나름 괜찮다 생각했건만 시간초과... ㅠㅠ
def solution(clothes):
    answer = 0
    data = {}
    for item in clothes:
        name, kind = item
        if kind in data:
            data[kind] += 1
        else:
            data[kind] = 1
    
    
    case = []
    
    
    for key in data:
        if len(case) == 0:
            case.append(data[key])
        else:
            origin_length = len(case)
            for i in range(origin_length):
                case.append(case[i] * data[key])
            case.append(data[key])
            
    answer = sum(case)
    
    return answer

3. (정답) 힌트를 보고 풀었다. 아무것도 안 입는 경우만 제외해주면 되는 간단한 문제였다... 고등학교 때 확률과 통계 약했는데 그게 여기서 티가 날 줄이야
   우선, 착용할 수 있는 모든 경우의 수를 구하려면 각 카테고리 별 요소의 수를 곱해야 한다. 하지만 아무것도 안 입는 경우를 고려해야 하므로 +1 해준다. 그러고 아무것도 입지 않았을 때의 경우만 빼주면 된다.

def solution(clothes):
    answer = 1
    data = {}
    for item in clothes:
        name, kind = item
        if kind in data:
            data[kind] += 1
        else:
            data[kind] = 1
    
    for key,value in data.items():
        answer *= (value + 1)
    
    answer -= 1
    
    return answer

Lv 3. 베스트 앨범

딕셔너리 d에 key로는 장르명, value로는 (재생횟수, 고유인덱스) 값을 부여했다.
딕셔너리 count에 key로는 장르명, value로는 총 재생횟수의 총합을 구했다. 처음 reduce함수를 사용해봤다!

reduce 함수

reduce 함수는 파이썬3부터는 내장함수가 아니어 import를 해줘야 한다.

from functools import reduce

reduce 함수는 (집계함수, 순회가능한 데이터[, 초기값])을 갖는다. 따라서 집계함수를 위해 lambda를 사용했다.

조건에 맞춰서 데이터를 뽑으면 끝~!

# 한방에 통과해서 조금 눈물이 났다 기쁨의 눈물이...
from functools import reduce
def solution(genres, plays):
    answer = []
    
    d = {}
    for i in range(len(genres)):
        if genres[i] in d:
            d[genres[i]].append((plays[i], i))
        else:
            d[genres[i]] = [(plays[i], i)]
    
    count = {}
    for key in d.keys():
        d[key].sort(reverse=True, key=lambda x: (x[0], -x[1]))
        # 재생횟수만 누적합
        count[key] = reduce(lambda acc, cur: acc + cur[0], d[key], 0) 
    
    # [('장르명', 재생횟수 총합)]
    sort_count = sorted(count.items(), key=lambda item: -item[1] ) 
    
    for item in sort_count:
        key = item[0]
        
        if len(d[key]) == 1:
            answer.append(d[key][0][1])
        else:
            answer.append(d[key][0][1])
            answer.append(d[key][1][1])
            
    return answer