[파이썬] 코딩테스트 문제 풀이 - 해쉬 문제 (프로그래머스)

Writer: Harim Kang

해쉬 알고리즘 문제 - 프로그래머스

해쉬 알고리즘 문제들은 파이썬의 딕셔너리를 사용하는 문제입니다. 해쉬 구조와 관련된 내용은 아래의 포스팅에 있습니다. 문제의 코드들은 다 통과를 한 코드입니다.

https://davinci-ai.tistory.com/19

파이썬으로 구현하는 자료구조 요약 정리 - 해쉬 테이블(Hash Table)

또한, 해당 포스팅에서 푸는 문제는 아래의 4가지 문제입니다.

1. 완주하지 못한 선수
2. 전화번호 목록
3. 위장
4. 베스트 앨범

해당 문제들은 프로그래머스의 코딩테스트 연습 > 코딩테스트 고득점 kit > 해시에 모여있는 4문제입니다.

https://programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

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

문제

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

문제 요약

• 마라톤에 참여한 선수 이름 배열 : participant
• 완주한 선수 이름 배열 : completion
• 위의 두 배열이 주어지고, 이때 완주 하지 못한 선수의 이름을 return하는 문제입니다.

테스트 케이스

주요 제한 사항

• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

해결

저는 hash라는 딕셔너리에 participant의 선수들 이름을 하나씩 key로 사용하여 딕셔너리에 이미 있으면 해당 key의 value를 1씩 증가시켜주는 방식으로 해결하였습니다. 1이면 동명이인이 없는 선수이며, 2이상이면 동명이인이 value값만큼 있다고 생각하면 됩니다.

hash를 다 완성하고, 완주자 명단인 completion의 선수들 이름을 하나씩 돌면서, 해당 key값의 value가 1이면 해쉬에서 해당 key, value를 삭제하였습니다. 그러면 동명이인이 아닌 완주자는 hash에서 사라집니다. 동명이인이 있어서, value가 2이상이면, 완주자 이름이 나올 때마다 -1을 해주는 방식입니다.

코드

def solution(participant, completion):
    hash ={}
    for i in participant:
        if i in hash:
            hash[i] += 1
        else:
            hash[i] = 1
    for i in completion:
        if hash[i] == 1:
            del hash[i]
        else:
            hash[i] -= 1
    answer = list(hash.keys())[0]
    return answer
#성공

2. 전화번호 목록 (Level 2)

해당 문제는 해쉬를 사용하지 않고, 리스트와 조건문만을 사용하여 풀었습니다..!

문제

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

문제 요약

• phone_book : 전화번호부 배열이 주어집니다.
• 한 번호가 전화번호부의 다른 번호의 접두어인 경우가 존재하면 false, 없으면 true를 return합니다.

테스트 케이스

해결

저는 전화번호부 리스트를 먼저 길이를 기준으로 오름차순으로 정렬해주었습니다. 그리고 해당 배열을 하나씩 짧은 번호들 부터 for문을 돌면서, 뒤의 번호들과 비교를 하였습니다. 접두어가 존재하면 answer을 False로 바꾸고, finish라는 변수에 True라고 선언하여, 함수를 끝내도록 구현하였습니다.

접두어가 존재하지 않으면 for문을 다돌고 True로 반환합니다.

코드

def solution(phone_book):
    answer = True
    finish = False
    phone_book = sorted(phone_book, key=len)
    for i in range(0, len(phone_book)):
        if finish:
            break
        current = phone_book[i]
        for j in range(i+1, len(phone_book)):
            comp = phone_book[j]
            if len(current)<len(comp) and current == comp[0:len(current)]:
                answer = False
                finish = True
                break
    return answer
#성공

3. 위장 (Level 2)

문제

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

문제 요약

• clothes : [옷의 이름, 옷의 종류]로 구성된 여러개의 배열이 담긴 배열이 주어집니다.
• 같은 종류의 옷은 동시에 2개 이상을 입을 수 없습니다.
• 옷은 최소 한개의 의상을 입어야합니다.
• 가능한 조합의 수를 return하는 문제입니다.

테스트 케이스

해결

저는 closet이라는 딕셔너리에 옷의 종류를 key로 옷의 이름들을 배열 형태로 담았습니다.

그리고, num_category라는 옷의 종류마다 옷의 갯수를 담은 배열을 만들었습니다.

총 옷 조합의 수는 (각 종류 마다 옷의 갯수+1)를 다 곱한 후 -1을 하면 나옵니다.

코드

def solution(clothes):
    closet = dict()
    num_category = []
    answer = 1

    for name, category in clothes:
        if category in closet:
            closet[category].append(name)
        else:
            closet[category] = [name]

    for key in closet.keys():
        num_category.append(len(closet[key]))

    for i in num_category:
        answer *= (i+1)
    answer -= 1

    return answer
#성공

4. 베스트 앨범 (Level 3)

문제

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

문제 요약

• genres[i] : 고유번호가 i인 노래의 장르
• plays[i] : 고유번호가 i인 노래의 재생 횟수
• 베스트 앨범은 아래와 같은 규칙으로 선정합니다.
  1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
  2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
  3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
  4. 위의 규칙으로 장르당 최대 2곡을 선정하여 앨범에 수록합니다.

테스트 케이스

해결

• song : dict, 노래의 장르를 key로, [(-1)*노래의 재생횟수, 노래의 고유번호]의 배열을 value로 담은 딕셔너리입니다. -1을 곱한 이유는 가장 큰 수를 작은 수로 바꾸면서 sort시에 첫번째는 노래 재생횟수로, 두번째는 고유번호로 정렬하기 위해서입니다. 그냥 sort에 reverse하면 고유번호를 고려해주지 못하기때문에 해당 방법을 사용하였습니다.

    if genre in song:
        song[genre].append([(-1)*num_play, i])
        song[genre].sort()
    else:
        song[genre] = [[(-1)*num_play, i]]

• sum_play : dict, 장르를 키 값으로 하여 각 장르의 총 재생 시간을 저장한 딕셔너리입니다.

    if genre in sum_play:
        sum_play[genre] += num_play
    else:
        sum_play[genre] = num_play

• 아래의 코드를 사용하여 sum_play를 총 재생시간 순으로 정렬해줍니다. 이때는 sort 기준이 두가지가 아니므로 그냥 sort(reverse=True)를 사용하였습니다.

    sorted_list = []
    for k in sum_play.keys():
        sorted_list.append([sum_play[k], k])
    sorted_list.sort(reverse=True)

• 마지막으로, 총 재생 시간이 높은 순서로 장르를 sorted_list에서 꺼내서, 베스트 앨범 목록인 answer에 그에 맞는 고유 번호를 두개 꺼냅니다. 이때, 장르에 노래가 하나가 있는 경우를 고려해주어야합니다.

    for _, g in sorted_list:
        for i in range(2):
            answer.append(song[g][i][1])
            if len(song[g]) == 1:
                break

코드

def solution(genres, plays):
    song = dict()
    sum_play = dict()
    n = len(genres)
    answer = []

    for i in range(n):
        genre = genres[i]
        num_play = plays[i]
        if genre in song:
            song[genre].append([(-1)*num_play, i])
            song[genre].sort()
        else:
            song[genre] = [[(-1)*num_play, i]]

        if genre in sum_play:
            sum_play[genre] += num_play
        else:
            sum_play[genre] = num_play
    sorted_list = []
    for k in sum_play.keys():
        sorted_list.append([sum_play[k], k])
    sorted_list.sort(reverse=True)

    for _, g in sorted_list:
        for i in range(2):
            answer.append(song[g][i][1])
            if len(song[g]) == 1:
                break
    return answer