[프로그래머스] 해시

shsh·2021년 9월 2일

프로그래머스

목록 보기

3/17

전화번호 목록 - Level 2

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

내 풀이 - 정확성: 83.3 | 효율성: 16.7 | 합계: 100.0 / 100.0

def solution(phone_book):
    phone_book.sort(key=len)
    prefix = set()
    for p in phone_book:
        for i in range(1, len(p)):
            if p[:i] in prefix:
                return False
        prefix.add(p)
    
    return True

길이 기준으로 정렬한 후

짧은 애들부터 prefix 에 넣어주면서
다음 번호들의 시작 값이 prefix 인지 확인

위장 - Level 2

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

내 풀이 - 정확성: 28.6 | 합계: 28.6 / 100.0

import collections

def solution(clothes):
    dic = collections.defaultdict(list)
    combinations = set()
    for c in clothes:
        dic[c[1]].append(c[0])
        combinations.add(c[0])
    
    types = list(dic.keys())
    
    def combination(types, comb):
        if comb:
            combinations.add(comb)
            
        if len(types) == 0:
            return
            
        for c in dic[types[0]]:
            combinations.add(c)
            combination(types[1:], comb+c)
    
    combination(types, "")
        
    return len(combinations)

우선 옷의 종류와 이름을 묶어주는 dic 생성
combinations 에는 옷의 이름들을 넣어주기 => set 로 중복 X

types 는 옷의 종류들만 저장

재귀 함수로 조합 찾기
모든 comb 조합들이 combinations 에 저장되면 최종적으로 길이 return

근데 안됨...

다른 사람 풀이 - 정확성: 100.0 | 합계: 100.0 / 100.0

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2
        else:
            clothes_type[t] += 1

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

    return cnt - 1

조합을 직접 찾지 않아도 개수로 계산 가능

옷의 종류별로 개수를 세준다
1 개만 입는 경우도 있으니까 초기값은 2, 나머지는 1 씩 추가

다 구해줬으면 종류별 개수를 곱해줌 => cnt

모두 안입은 경우 한가지를 빼주고 return

베스트앨범 - Level 3

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

내 풀이 - 정확성: 6.7 | 합계: 6.7 / 100.0

import collections

def solution(genres, plays):
    total = collections.defaultdict(int)
    gp = collections.defaultdict(list)
    top2 = collections.defaultdict(list)
    
    for i in range(len(genres)):
        total[genres[i]] += plays[i]
        gp[genres[i]].append((plays[i], i))
    
    for k, v in gp.items():
        v.sort(reverse=True)
        top2[k] = v[:2]
    
    genres = set(genres)
    
    ans = []
    ansGenres = []
    for g in genres:
        if len(ansGenres) == 0:
            ansGenres.append(g)
        elif len(ansGenres) == 1:
            if total[ansGenres[0]] > total[g]:
                ansGenres += [g]
            else:
                ansGenres = [g] + ansGenres
        else:
            for i in range(2):
                if total[ansGenres[i]] < total[g]:
                    ansGenres = ansGenres[:i] + [g] + ansGenres[i:len(ansGenres)-1]
                    
    for g in ansGenres:
        ans += [top2[g][0][1], top2[g][1][1]]
    
    return ans

total 은 각 장르마다 재생횟수를 묶어줌
ex) 'classic': 1450

gp 는 장르별 고유번호 재생횟수
ex) 'classic': [(500, 0), (150, 2), (800, 3)]

top2 는 장르별 재생횟수 상위 2
ex) 'classic': [(800, 3), (500, 0)]

total, gp 구하기
gp 기반으로 정렬하고 2개씩 잘라서 top2 구하기
중복 없이 genres 들을 보면서 재생횟수가 가장 높은 2 가지의 장르 선별
=> 재생횟수 비교해서 순서 update
두 장르의 top2 고유 번호만 ans 에 저장 후 return

다른 사람 풀이 - 정확성: 100.0 | 합계: 100.0 / 100.0

def solution(genres, plays):
    answer = []
    
    d = {e:[] for e in set(genres)}
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1] , e[2]])
        
    genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True)
    
    for g in genreSort:
        temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
        answer += temp[:min(len(temp),2)]
        
    return answer

d 에 우선 장르들만 key 값으로 저장

각 장르마다 (재생횟수, 고유번호) 묶어서 저장

genreSort: 장르별 전체 재생횟수를 기준으로 정렬
=> x: sum(map(lambda y: y[0],d[x]))

genreSort 의 장르들을 보면서 상위 2 개의 고유번호 추출
=> 장르별 (재생횟수, 고유번호) 들을 역순으로 정렬하고 2 개까지 slice