[PROGRAMMERS] 프로그래머스 코딩테스트 연습 > 해시(hash) 파이썬 문제풀이

프로그래머스 코딩테스트 연습 > 고득점 kit > 해시(hash) 파트 파이썬 문제풀이 https://programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

 

해시 테이블(Hash Table)

키(key)에 값(value)을 저장하는 구조로 파이썬에서는 딕셔너리(사전) 자료형 이용

- 해시 : 임의 값을 고정 길이로 변환하는 것

- 해시 테이블 : 키 연산을 통해 직접 접근이 가능한 데이터 구조

- 해싱 함수 : 키에 대해 연산을 통해 데이터 위치를 찾을 수 있는 함수

- 해시 값(주소) : 키를 해싱 함수로 연산하여 해시 값을 알아낸 뒤 이를 이용하여 해시 테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수있음

- 슬롯 : 한 개의 데이터를 저장할 수 있는 공간

 

파이썬에서 해시 함수

hash(data)

* 보안 문제로 인해 파이썬 3.3부터 프로그램 재시동시마다 해시값이 달라짐

 

암호학적 해시 함수

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1() # SHA-1
hash_object = hashlib.sha256() # SHA-256
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print(hex_dig)

 

 

완주하지 못한 선수 (Level 1)

 내 코드 

def solution(participant, completion):
    answer = ''
    
    for p in participant:
        if p in completion:
            completion.remove(p) # 완주한 선수인 경우 제외 
        else:
            answer = p # 완주하지 못한 선수
            
    return answer

경기에 참여한 선수 목록과 완주한 선수 목록을 비교해야된다고 생각하여 in, not in 메서드를 이용하였다. 하지만 in 메서드도 순회하며 비교하기 때문에 역시나 O(n) 시간복잡도를 갖는다. 결국 내 코드는 O(n^2).. 그래서 효율성 검사에서 통과가 안된듯 하다.

 

* in() 시간복잡도 최선 O(1) ~ 최악 O(n)

 

 다른 사람 코드 1 

def solution(participant, completion):
    answer = ''
    dict = {}
    temp = 0
    
    for p in participant:
        dict[hash(p)] = p
        temp += int(hash(p)) # 모든 해시값 저장

    for c in completion:
        temp -= int(hash(c)) # 완주한 선수의 해시값 삭제
    
    answer = dict[temp] # 완주하지 못한 선수 1명의 해시값만 남음

    return answer

해시 함수로 생성된 해시 값이 한 프로그램내에서는 동일하다는 점과 완주하지 못한 선수가 1명이라는 조건을 잘 이용하였다.

 

 다른 사람 코드 2 

import collections

def solution(participant, completion):
    # 참여선수 빈도수 - 완주선수 빈도수
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

나는 가급적 외부 모듈을 안불러와서 쓰려고 했는데 자주 사용되는 모듈이나 성능에 큰 도움을 주는 모듈들은 좀 알아둬야겠다고 생각했다..

collections.Counter 가 산술, 집합 연산이 가능하다는 점을 잘 살렸다.

participant와 completion의 선수 빈도수를 세고 참여에서 완주를 뺀다. counter는 알아서 빈도수 내림차순으로 정렬되는데, 참여했으나 완주하지 못한 선수 1명의 answer value 값이 1이기 때문에 answer 가장 앞에 오게 된다 (동명이인도 쉽게 같이 해결).

 

 다른 사람 코드 3-1 

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    return participant[len(participant)-1]

이름을 정렬한 후 한 for문에서 두 선수 리스트를 함께 돌아 시간복잡도를 줄였다.

두 리스트를 한번에 순회하는게 좋을거같은데.. 라고 생각은 했었는데 저 정렬하는걸 생각못해내서 난 이중for문 썼었다ㅠㅠ 아숩

 

 다른 사람 코드 3-2 

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for p, c in zip(participant, completion):
        if p != c:
            return p
    return participant[-1]

3-1과 동일하지만 zip() 메서드로 좀 더 간편하게 표현

* zip() : 여러 개의 순회 가능한(iterable) 객체를 인자로 받아 각 객체가 담고 있는 원소를 튜플 형태로 차례로 접근할 수 있도록 함

 

 

전화번호 목록 (Level 2)

 내 코드 

def solution(phone_book):
    answer = True
    
    phone_book.sort()

    for i in range(len(phone_book) - 1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    
    return answer

번호가 문자열이고 한 번호가 다른 번호의 접두사인지 판단해야한다는 것에 초점을 맞춰 startswith() 를 사용했다.

그리고 접두사를 찾았을 때 바로 false를 반환하여 무의미한 반복문을 돌지 않도록 성능을 조금이나마 높히려 애썼다..!

 

* str.startwith() : 인자로 주어지는 문자열이나 튜플(문자열로 이뤄진)로 시작되는지 True/False 반환

 

 다른 사람 코드 1 

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False

    return True

나와 원리는 동일하나 zip 메서드 사용

 

 다른 사람 코드 2 

def solution(phone_book):
    answer = True
    dict = {}

    for phone_number in phone_book:
        dict[phone_number] = 1 # 번호(key)에 대한 value 1로 초기화
    
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in dict and temp != phone_number:
                answer = False
    
    return answer

주제가 해시인 만큼 문제 취지에 잘 맞는 코드라는 평을 보고 살펴봤는데.. 성능은 잘 모르겠다.

 

 

위장 (Level 2)

이 문제에서 중요한 것은 식을 세우는 것! 예를 들어 의상 종류가 3개이고 각 의상 종류별 의상의 수가 3, 4, 2개라면 -> (3+1) * (4+1) * (2+1) - 1

종류별 의상 수에 1을 더하는 이유는 해당 종류를 아예 착용하지 않았을 경우를 더해준 것이고 마지막에 1을 빼는 경우는 아무 의상도 착용하지 않았을 경우를 뺀 것이다.

경우의 수를 생각하면 쉽게 떠올릴 수 있음!

 

 내 코드 

def solution(clothes):
    answer = 1
    clothes_dict = {} # 의상 종류별 의상 수 저장하는 딕셔너리
    clothes_list = [] # 의상 종류 (중복제거)

    for c in clothes:
        clothes_dict[c[1]] = 0 # 종류별 의상 수 0으로 초기화
        clothes_list.append(c[1])

    for c in clothes:
        clothes_dict[c[1]] += 1 # 종류별 의상 수 count
        
    clothes_list = list(set(clothes_list)) # set() 중복제거

    for i in range(len(clothes_list)):
        answer *= (clothes_dict[clothes_list[i]] + 1)
        
    return answer - 1

딕셔너리 초기화할 때 collections.defaultdict() 을 써도 될것같다.

 

 다른 사람 코드 1 

def solution(clothes):
    clothes_type = {}

    for _, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2 # 한 의상 종류의 첫 옷이 등장할 때 초기화
        else:
            clothes_type[t] += 1 # 같은 종류의 다른 옷이 있을 때 의상 수 증가

    answer = 1
    for num in clothes_type.values():
        answer *= answer

    return answer - 1

나와 비슷한데 나중에 계산할 때 1을 더해야되는 것을 염두해두고 의상이 있을 때 초기값을 2로 두신 듯하다.

 

 다른 사람 코드 2 

from collections import Counter
from functools import reduce

def solution(clothes):
    cnt = Counter([kind for name, kind in clothes]) # 의상명, 의상 종류 중 의상 종류 count
    answer = reduce(lambda x, y: x * (y + 1), cnt.values(), 1) - 1
    return answer

종류별 의상 수를 세야함으로 collections.Counter() 을 쓰기 좋은 문제인거 같다.

간단한 for문을 한줄에 쓰거나 lambda 함수 사용이 아직 익숙치 않은데 나도 저렇게 잘 써보고싶다..

 

* reduce() : 주로 여러 데이터를 대상으로 누적 집계를 낼 때 사용

reduce(집계 함수, 순회 가능한 데이터 [, 초기값])

 

 

베스트 앨범 (Level 3)

답안 정렬 순서 헷갈리지 말 것 + 각 장르마다 2곡씩만 추천

속한 노래가 많이 재생된 순서대로 장르 정렬 > 각 장르마다 가장 많이 재생된 두 곡 추천 (같은 장르, 재생수인 곡은 고유번호가 낮은 곡 우선)

 

 내 코드 

from collections import defaultdict

def solution(genres, plays):
    answer = []
    
    # for g in genres_list:
    #     genres_dict[g] = 0
    genres_dict = defaultdict(int) # 장르별 곡 수 0으로 초기화
    plays_dict = defaultdict(list) # 장르별 곡 리스트 저장을 위해 리스트로 초기화
    
    for i, [g, p] in enumerate(zip(genres, plays)):
        genres_dict[g] += p # 장르별 재생수
        plays_dict[g].append((i, plays[i])) # tuple형태로 곡 인덱스와 재생수 저장
    
    # 재생수 기준(value) 내림차순 정렬
    genres_dict = sorted(genres_dict.items(), key=lambda item: item[1], reverse=True)

    # for value in plays_dict.values():
    #     value.sort(key=lambda x: x[1], reverse=True)

    for key, value in genres_dict:
        # value(tuple[1]) 기준 정렬
        musics = sorted(plays_dict[key], key=lambda x: x[1], reverse=True)[:2]
        for _, i in musics:
            answer.append(_)
        
    return answer

genres_dict 은 장르별 곡 재생수의 합 이고 plays_dict 은 장르를 key 값으로 value에 (곡 인덱스, 곡 재생수) 형식의 튜플 리스트 를 담았다.

원래 장르별 노래 재생수 기준 내림차순 정렬을 for문으로 하고 다른 for문에서 answer에 추가해줬는데 굳이 반복문 두번 돌릴 필요 없을거같아 합쳐주었다.

 

이 문제는 다들 비슷비슷하게 푼 것 같다!

 

 

* 딕셔너리 정렬

- 키 기준

sorted(dict.keys()) # 오름차순
sorted(dict.keys(), reverse=True) # 내림차순

- 값 기준

# items() -> item[0] key, item[1] value
sorted(dict.items(), key = lambda item: item[1]) # 내림차순
sorted(dict.items(), key = lambda item: item[1], reverse=True) # 오름차순

 

* 튜플 정렬

- 첫번째 값 기준

sort(key=lambda x: x[0]) # 오름차순
sort(key=lambda x: -x[0]) # 내림차순

- 두번째 값 기준

sort(key=lambda x: x[1])

- 첫번째 값 기준 > 두번째 값 기준

sort(key=lambda x: (x[0], x[1]))

 

* sort()와 sorted() 인자 설정 동일 (참고 https://juran-devblog.tistory.com/58) 

sorted() : 원래의 데이터는 두고 새로운 정렬된 데이터 반환

sort() : 해당 배열 자체를 정렬하여 반환

 

 

 

참고

시간복잡도 - https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리

zip 메서드 - https://www.daleseo.com/python-zip/

[파이썬] 내장 함수 zip 사용법

reduce 메서드 - https://www.daleseo.com/python-functools-reduce/

파이썬 reduce 함수 사용법