[프로그래머스/고득점 Kit] Hash

ZenTechie·2023년 5월 1일

PS

목록 보기

12/53

해시

Key-value쌍으로 데이터를 빠르게 찾아보세요.

출제 빈도	평균 점수	문제 세트
높음	보통	5 / 5

폰켓몬

def solution(nums):
    max_pick = len(nums) // 2 # 가져갈 폰켓몬 개수
    unique_nums = set(nums) # 중복 제거
    
    # 모두 다른 폰켓몬이면 N // 2개가 최대이다.
    # 그러나 중복을 제거한 후 폰켓몬의 종류가 N // 2보다 적다면, 
    # 현재 가지고 있는 폰켓몬의 종류의 개수가 최대가 된다.
    return min(len(unique_nums), max_pick)

풀이

가지고 있는 폰켓몬은 중복되는 종류도 포함되므로, 먼저 중복을 제거한다.

중복을 제거했을 경우 다음 경우의 수가 존재한다.

폰켓몬의 종류가 N // 2개보다 많거나 같은 경우
폰켓몬의 종류가 N // 2개보다 적은 경우

폰켓몬의 종류가 N개로 그대로인 경우는 N // 2개를 그대로 return한다.
하지만, 폰켓몬의 종류가 N // 2개보다 적을 경우, N // 2개를 뽑을수가 없다.
따라서, 이때는 가지고 있는 폰켓몬의 종류를 return한다.

완주하지 못한 선수

from collections import Counter

def solution(participant, completion):
    p = Counter(participant)
    c = Counter(completion)
    
    return list((p - c).keys())[0]

풀이

문제에서 완주하지 못한 선수는 단 한 명이라고 주어진다.
먼저, Counter를 사용해서 인자로 주어지는 participant와 completion을 모두 Counter 객체로 변환한다.
(p = Counter(particiapnt), c = Counter(completion))

그 후, p에서 c를 빼준다.
즉, 참가자 명단에서 완주자 명단을 빼주므로, 완주하지 못한 사람을 얻을 수 있다.

이때 Counter 객체는 dictionary이고 우리가 원하는 것은 (p - c).keys()이다.
하지만 keys()는 Object를 반환하므로, list로 변환해야 한다.
따라서, list((p - c).keys())[0] 이 구하고자 하는 답이 된다.
(key : 참가자 이름, value : 수)
(완주하지 못한 사람은 단 1명이므로 [0]을 사용한다.)

전화번호 목록

def solution(phone_book):
    phone_book.sort() # O(NlogN)
    
    for i in range(len(phone_book) - 1):
        p1, p2 = phone_book[i], phone_book[i + 1]
        if p2.startswith(p1):
            return False
        
    return True

phone_book의 길이는 1 이상 1,000,000 이하이므로,
$O(N^2) = 1,000,000,000,000$ 으로 시간초과가 발생한다.

따라서, 다른 방법을 찾아야 한다.

만약, 어떤 번호가 다른 번호의 접두어라면 phone_book을 정렬했을 때 이 둘은 서로 인접하게 위치한다.

따라서, 현재 인덱스가 i 라면, i + 1 의 값과 비교하면 된다.

그러므로, 먼저 phone_book.sort() 후 i와 i + 1의 번호를 각각 가져온다.
그리고 startswith() 를 사용해서 접두어인지 판별한다.

총 시간복잡도는 sort 의 $O(NlogN)$ 이다.
(startswith()의 시간복잡도도 영향이 있을 것 같은데,, 찾아봐도 시간복잡도가 얼마인지 안나온다..)
그런데 일단 효율성도 통과하는 것을 보아, startswith를 고려해도 $O(N^2)$ 를 넘지는 않는 것 같다.

의상

from collections import defaultdict

def solution(clothes):
    answer = 1
    
    # 경우의 수를 세면 되므로, int로 설정하면 됨
    # 굳이 list로 할 필요 없다.
    _dict = defaultdict(int) # key : 옷 종류, value : 옷의 개수 
    
    for cloth in clothes:
        key = cloth[1] # 옷의 종류
        _dict[key] += 1 # 옷의 개수 + 1 
        
    # 모든 경우의 수 계산
    for key in _dict.keys():
        answer *= (_dict[key] + 1)
    
    # 모두 안입는 경우를 뺴준다.
    return answer - 1

defaultdict 를 사용한다. 이때 value를 list로 만들어서 옷의 이름을 추가할 필요는 없다.
우리가 구하고자 하는 것은 옷을 입는 경우의 수 이므로, 각 옷의 종류별로 몇벌의 옷이 있는지만 count 하면 된다.

따라서, defaultdict의 Type = int 로 설정한다.

그리고 경우의 수를 계산하자.
예를 들어 옷의 종류와 개수가 다음과 같다고 가정하자.

headgear	glasses
2개(hat, turban)	1개(sunglasses)

headgear인 경우
1. hat을 입는 경우
1. turban을 입는 경우
2. headgear를 입지 않는 경우
glasses인 경우
1. sunglasses를 입는 경우
1. glasses를 입지 않는 경우

이 경우에는 3 * 2 로 총 6가지의 경우의 수가 존재한다.
하지만, 둘 다 입지 않는 경우가 포함되어 있고 이는 문제의 조건에 위배되므로 -1 을 해준다.
따라서, 최종적으로는 5가지 가 된다.

즉, 옷의 종류에 따른 개수가 a, b, c 일 때 위의 식을 일반화하면,
전체 경우의 수 = (a + 1)(b + 1)(c + 1) - 1 이다.

베스트앨범

from collections import defaultdict

def solution(genres, plays):
    answer = []
    _dict = defaultdict(list) # key: 장르 , value : [(고유번호, 재생횟수), ...]
    
    # 장르, (고유번호, 재생횟수) 합치기
    _list = list(zip(genres, enumerate(plays)))
    
    # 많이 재생된 노래 기준으로 오름차순 정렬
    # 재생 횟수가 같다면 고유 번호를 기준으로 내림차순 정렬
    _list.sort(key=lambda x: (-x[1][1], x[1][0]))
    
    # 딕셔너리 초기화
    for val in _list:
        # 장르, (고유번호, 재생 횟수)
        genre, play = val
        _dict[genre].append((play[0], play[1]))
    
    # 속한 노래가 많이 재생된 장르 기준으로 정렬
    # sum(list(zip*x[1]))[1])은 각 장르의 재생횟수들의 합을 계산한다.
    # 이를 내림차순으로 정렬한다.
    sorted_dict = sorted(_dict.items(), key=lambda x: -sum(list(zip(*x[1]))[1]))
    
    # 노래가 많이 재생된 장르로 정렬이 이미 되어있다.
    for x in sorted_dict:
    
        music_list = x[1] # (고유번호, 재생횟수)
        answer.append(music_list[0][0]) # 장르에 속한 곡이 하나라면, 하나의 곡만 선택
        
        # 총 2개의 곡을 수록한다.
        if len(music_list) >= 2: # 속한 곡이 2개 이상이라면, 하나 더 추가
            answer.append(music_list[1][0])
    
    return answer

문제의 조건은 다음과 같다.

속한 노래가 많이 재생된 장르를 먼저 수록한다.
장르 내에서 많이 재생된 노래를 먼저 수록한다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.

위의 조건과 문제에서 인자로 주어지는 genres, plays를 살펴보았을 때 장르가 여러개가 있을 수 있고 이를 key로 하며, 각 장르에 속하는 노래의 재생 횟수를 value로 가지는 dictionary를 사용해야겠다고 생각했다.

dictionary를 초기화하기 전에, [장르, (고유번호, 재생횟수)] 형태로 list를 하나 생성했다.

왜냐하면, 조건 2, 3번을 처리하기 위함이다.
이는 sort(key=lambda x: (-x[1][1], x[1][0])) 을 사용해서 처리한다.
-x[1][1] 은 재생횟수를 기준으로 내림차순 정렬을 의미하고
x[1][0] 은 고유 번호를 기준으로 오름차순 정렬을 의미한다.

그 후, 딕셔너리를 초기화한다.(key = 장르, value : (고유번호, 재생횟수))

이제 조건 2, 3번은 처리했으므로 1번만 처리하면 된다.
dictionary의 items()를 정렬하되, 이제는 속한 노래가 많이 재생된 장르를 기준으로 내림차순 정렬해야 한다.

속한 노래의 재생 횟수는 것은 각 장르의 value에 속한 재생횟수들의 합을 의미한다.
따라서, dictionary의 items()를 정렬할 때 lamda를 사용하여,
-sum(list(zip(*x[1]))[1]))을 기준으로 내림차순 정렬한다.
zip(*x[1])) 에서 x[1]은 value를 의미한다.