[Python] 프로그래머스 코딩테스트 고득점 Kit - 해시

출처: 위키피디아

---

1. 폰켓몬 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/1845

# 이해
# N마리 중에서 N/2마리를 선택.
# 이때 가장 많은 종류를 선택하고, 그때의 가짓수를 return
# nums의 길이는 10,000이므로 O(n^2)까지는 괜찮겠다. 프로그래머스는 10억에서 시간 초과가 발생하므로.

# 풀이
# nums+1(0부터 200,000) 크기의 visited 배열을 만든다.
# nums를 탐색하며, 방문하지 않은 포켓몬일 경우 result, cnt에 += 1 하고, 방문 처리한다.
# 매 탐색마다 cnt가 len(nums) // 2 이하인지 확인한다. 초과하면 result를 return 한다.

def solution(nums):
    return min(len(nums) // 2, len(set(nums)))

 

최초에는 방문 처리를 통해 최소 횟수로 최대 개수를 확보하려고 했다.

그러나 모든 포켓몬이 다른 종류인 경우 최대 방문 가능 횟수(`len(nums) // 2`) == 정답이다.

포켓몬의 종류가 `len(nums) // 2`보다 작은 경우 그것이 정답이다.

 

 

2. 완주하지 못한 선수 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/42576

 

최초 풀이 (정렬)

# 이해
# completion에 있지만, participant에 없는 사람 return
# 동명이인이 있을 수 있다.

# 풀이
# 정렬한다.
# 순서대로 나오지 않으면 즉시 return 한다.

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]

 

더 나은 풀이 (hash 함수)

def solution(participant, completion):
    
    dic = {}
    tmp = 0
    
    for part in participant:
        dic[hash(part)] = part
        tmp += hash(part)
    
    for comp in completion:
        tmp -= hash(comp)
        
    return dic[tmp]

 

hash 함수의 성질을 이용한 풀이이다.

배열의 각 원소를 탐색하며, hash()로 생성된 고유 숫자를 더하고 빼면, 하나의 고유 숫자만이 남는다는 것을 응용했다.

 

 

3. 전화번호 목록 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42577

# 이해
# 어떤 번호가 다른 번호의 접두어인 경우 false
# 아니라면 true
# str.startswith() / str.endswith() -> Bool

# 풀이
# phone_book을 탐색하며, 딕셔너리에서 현재 단어가 없다면,
# 현재 단어를 1글자씩 tmp에 더해가며 딕셔너리가 True가 반환되는 것이 있는지 확인.
# 있으면 return 없으면 완성된 단어를 True로 갱신


def solution(phone_book):
    dic = {}
    
    for pb in phone_book:
        dic[pb] = 1
    
    for pb in phone_book:
        tmp = ""
        for pb_chr in pb:
            tmp += pb_chr
            if tmp in dic and tmp != pb:  # 여기서도 동일하게 'if' 사용
                return False
    
    return True

 

단어 배열을 탐색하며, 완성된 단어는 모두 방문 처리한다.

단어 배열을 다시 탐색하며, 각 단어를 이중 탐색한다.

 

한 글자씩 더해가며 딕셔너리에 있는 단어인지 판단한다.

이때, 한 글자씩 더해가다가 단어가 완성된 경우는 제외한다. 문제의 조건에 중복된 단어는 없기 때문이다

 

 

4. 의상 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42578

# 이해
# 패션 조합의 가짓수
# 하루에 최소 한 개의 의상
# 한 종류에서는 하나의 옷만 선택
# 모든 종류를 선택할 수도, 하나의 종류만 선택할 수도, 복수의 종류만 선택할 수도 있다.

# 풀이
# from itertools import combinations
# type별로 카운트 횟수를 딕셔너리에 기록함
# type에 대한 조합을 구함.
# 모든 조합에 대하여, type에 대응하는 카운트 횟수를 곱해 answer에 더함.
# answer 반환.

def solution(clothes):
    answer = 1  # 곱셈을 위해 1부터 시작
    dic = {}
    
    # 각 옷의 종류별로 개수를 계산
    for _, type in clothes:
        dic[type] = dic.get(type, 0) + 1
    
    # 각 종류별로 옷을 선택하는 경우의 수 계산 (해당 종류의 옷을 안 입는 경우 포함)
    for count in dic.values():
        answer *= (count + 1)  # 해당 종류의 옷을 선택하지 않는 경우도 포함하여 +1
    
    return answer - 1  # 아무것도 입지 않는 경우의 수 1을 뺌

 

최초에는 combinations를 사용하여 복잡하게 풀이했다.

더 나은 풀이를 참고하니 깨달음을 얻었다.

 

선택하지 않는 것을 포함한 모든 조합의 수를 구하는 것 == 케이스마다 선택 가능한 `경우의 수 + 1` 모두 곱하기

 

 

5. 베스트앨범 (Lv. 3)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

# 이해
# 1. 해당 장르의 재생 수
# 2. 동일 장르 내 곡의 재생수
# 3. 고유번호가 낮은 것

# 풀이
# genre_count = { 장르: 총 재생 횟수 }
# genre_dic = { 장르: [고유번호, 재생 횟수] }
# genre_count -> 재생 횟수 -> 고유 번호 순서대로 정렬
# 각 장르마다 2개씩 끊어서 고유 번호 저장

def solution(genres, plays):
    answer = []
    
    genre_count = {}
    genre_dic = {}
    
    for i in range(len(genres)):
        if genres[i] in genre_count:
            genre_count[genres[i]] += plays[i]
        else:
            genre_count[genres[i]] = plays[i]
        
        genre_dic.setdefault(genres[i], []).append([i, plays[i]])
    
    # genre_count의 values의 내림차순으로 정렬
    genre_count_sorted = sorted(genre_count.items(), key=lambda x: x[1], reverse=True)
    
    for genre, _ in genre_count_sorted:
        sorted_songs = sorted(genre_dic[genre], key=lambda x: (-x[1], x[0]))
        answer.extend([song[0] for song in sorted_songs[:2]])
    
    
    return answer

 

최초에는 정말 복잡하게 풀었다.

 

`dictionary.setdefault(val, default_val)` 함수를 기억하자.

lambda로 정렬 함수를 작성할 때 `-, +` 부호를 활용하여 `내림차순, 오름차순`을 쉽게 표현할 수 있다는 것을 기억하자.

 

구현 문제가 아닌 이상 코딩테스트의 코드는 과도하게 복잡해지지 않는다는 것을 기억하자.

실전에서는 어찌 됐든 풀이하는 게 맞다. 그러나 코드의 엔트로피가 올라가고 있다면 뭔가 잘못 됐다는 것을 의식하자.