[프로그래머스] 해시 2문제

💡 여러분 저는 해시 너무 생소합니다 (흑흑) 개념 공부부터 하고 올게요…

해시 개념

해시 개념

1. 의상

문제 설명

• 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

• 예제 #1 : headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.
  1. yellow_hat
  2. blue_sunglasses
  3. green_turban
  4. yellow_hat + blue_sunglasses
  5. green_turban + blue_sunglasses
• 예제 #2 : face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.
  1. crow_mask
  2. blue_sunglasses
  3. smoky_makeup

알고리즘

• hash

코드

def solution(clothes):
    # 1. 옷을 종류별로 구분하기
    hash_map = {}
    for clothe, type in clothes:
        hash_map[type] = hash_map.get(type, 0) + 1

    # 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
    answer = 1
    for type in hash_map:   
        answer *= (hash_map[type] + 1)

    # 3. 아무종류의 옷도 입지 않는 경우 제외하기
    return answer - 1

print(solution([["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]))

설명

• 비슷한 문제 (level1.완주하지 못한 선수)
  • https://coding-grandpa.tistory.com/85
• 나는 경우를 배열에 저장해두고 하나하나 체크하는걸 생각했는데 이방법은 훨씬 효율적인것같다.
• 종류마다 옷이 얼만큼 있는지에 따른 경우를 구한후 모든 종류별 경우를 곱한 뒤 아무 종류의 옷도 입지 않는 경우를 제한다.

[프로그래머스] 위장 (해시 Lv. 2) - 파이썬 Python

어려웠던 점

• 개념을 잘 몰라서 로직을 알것같아도 구현이 어려웠다.
  • 파이썬에서는 해시를 딕셔너리로 구현한다고는 하는데 그걸 할줄 모름.
• 고민해봐도 답이 안나와서
• 그래서 그냥 어떤식으로 하는지 보기 위해서 검색했다.
• Counter 라는 걸 사용하는 방법도 있다고 하는데 난 지금 해시도 어리바리라서 일단 넘긴다.

2. 베스트 앨범

문제 설명

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

알고리즘

hash

코드

def solution(genres,plays):
    answer =[]
    playDic = {} #{장르: 총 재생횟수}
    dic = {} # {장르 :[(플레이 횟수, 고유번호)]}

    # 해시 만들기
    for i in ragne(len(genres)):
        playDic[genres[i]] = playDic.get(genres[i],0) + plays[i] #장르에 맞는 value 가 없을경우 plays를 추가해준다.
        dic[genres[i]] = dic.get(genres[i],[])+[(plays[i],[i]) #장르에 맞는 value 가 없을 경우 [(재생횟수, index)] 딕셔너리를 추가해준다.

    #재생 횟수 내림차순으로 장르별 정렬
    genreSort = sorted(playDic.items(),key=lambda x:x[1],reverse = True)
    # playDic을 items()라는 함수를 사용해 튜플로 만듦. x[1]이니까 '총 재생 횟수'를 기준으로 내림차순(reverse = True) 정렬

    # 재생 횟수 내림차순, 인덱스 오름차순 정렬
  # 장르별로 최대 2개 선택
    for (genre, totalPlay) in genreSort:
        dic[genre] = sorted(dic[genre], key = lambda x: (-x[0], x[1])) #-x[0]의 마이너스는 내림차순의 의미
        answer += [idx for (play, idx) in dic[genre][:2]] #answer에 장르별로 최대 2개의 고유번호 추가

return answer

설명

(고민한 흔적)

• 장르 - 총 ! 재생횟수 / 장르 - 재생횟수 - index
  • 생각해보니 “총” 재생횟수는 고려하지 못했다.
  • 장르의 우선순위도 고려했어야 한다.
• 어떻게 장르 - play -index 를 엮을까를 고민을 많이 했었는데 이 해답에서는
  • {장르 : [(플레이, 고유번호)]} 로 해결했다 ..
  • 멋지다.

딕셔너리 Value값을 기준으로 정렬

• 딕셔너리에 items() 메서드를 사용해주면 {"key" : value}의 형태를 [(key, value)]의 형태로 만들어 준다.
• 이를 sorted해주면 key값을 기준으로 오름차순으로 정렬한다. value값으로 정렬하려면 lambda를 사용해주면 된다.

sorted(d.items(), key=lambda x : x[1])

어려웠던 점

• 배열 반복문 작성
• lambda 구문 작성
• 정렬
• 다