해시

1. 완주하지 못한 선수 lv.1

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion에서

완주하지 못한 선수 return하는 문제

<제한 사항>

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

def solution(participant, completion):
    # len(completion) = len(participant)-1
    # person=participant-completion
    # 딕셔너리
    
    dic={}
    total=0
    
    for p in participant:
        dic[hash(p)]=p
        total+=hash(p)
    for c in completion:
        total-=hash(c)
    
    return dic[total]

• 동명이인이 있을 수 있으며, 몇 명인지 모르므로 중복제거 할 수 없음!
• 완주하지 못한 선수가 여러 명이면 풀 수 없음

 

여러 명일 경우, 아래와 같이 풀면 된다. 

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())

 

 

 

2. 폰켓몬 lv.1

~~~

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return.

<제한 사항>

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

def solution(nums):
    # 중복값 제거, 중복값 적은 애들부터 선택해야 가장 많이 가져갈 수 있음
    species=list(set(nums))
        
    max=len(nums)//2
    l=len(species)
    
    # N/2 선택 가능하므로, N마리 종류가 N/2보다 크면 한마리씩 -> 선택할 수 있는 종 최댓값 == N/2
    if l>=max:
        return max
    else:   # N마리 종류가 N/2보다 작으면 적은 수의 종부터 선택 -> 선택할 수 있는 종 최댓값 == 종 수
        return l

 

한 줄로는 이렇게 풀 수 있다...

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

 

 

 

3. 전화번호 목록 lv.2

한 번호가 다른 번호의 접두어인 경우가 있는지 확인. 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return.

<제한 사항>

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

def solution(phone_book):
    # 문자열이므로, sort하면 글자순으로 묶임
    # 이전 원소가 다음 원소에 포함되어 있을 때, 접두사면 false
    
    #phone_book.sort()
    #for i in range(len(phone_book)-1):
        ## if not phone_book[i-1] in phone_book[i]:
        ##    return True
        #if phone_book[i]==phone_book[i+1][:len(phone_book[i])]:
            #return False
        #else:
            #return True
            
    dic = {}
    for phone_num in phone_book:
        dic[phone_num]=1    # 중복 전화번호 없음
    
    for phone_num in phone_book:                        # 123
        chkNum=''
        for numChar in phone_num:
            chkNum += numChar                           # 12
            if phone_num != chkNum and chkNum in dic:   # 12 != 123 and 12 in dic
                return False
        
    return True

 

 

정렬을 이용하여 인접한 데이터만 검사하면 되는 아이디어를 이용한 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

 

 

 

4. 의상 lv.2

매일 다른 옷 조합. 각 종류별로 최대 1가지 착용 가능. 일부가 겹쳐도 다른 의상이 겹치지 않으면 다른 방법으로 간주

<제한 사항>

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

def solution(clothes):
    # (A종류 옷 개수+1)*(B종류 옷 개수+1)* ... - 1
    # 2차원 배열 의상의 이름, 의상의 종류
    # dict{의상의 종류} = 개수
    
    dic={}
    for c, t in clothes:
        if t not in dic:
            dic[t] = 1
        else:
            dic[t] += 1
        
    answer=1
    for v in dic.values():
        answer *= v+1
        
    return answer-1

 

 

※ Counter 생성자는 여러 형태의 데이터를 인자로 받으며, 중복된 데이터는 몇 번 중복되는지 저장됨

(문자열이 인자인 경우, 각 문자가 문자열에 몇 개 포함되어 있는지 반환됨)

from collections import Counter
from functools import reduce

def solution(clothes):
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

 

 

 

 

 

5. 베스트앨범 lv.3

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

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

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

 

<제한 사항>

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

def solution(genres, plays):
    # 1. 장르별 총합
    # 최댓값에 중복 없음
    # if 최다 재생된 장르들 = [k for k,v in dic.items() if max(dic.values()) == v]
    dic={}
    for g,p in zip(genres, plays):
        if g not in dic:
            dic[g]=p
        else:
            dic[g] += p
            
    dic = sorted(dic.items(), key=(lambda x:x[1]), reverse=True)
    # 2. 장르 내 top2
    answer=[]
    for k,v in dic:
        #장르별 최다 플레이된 곡 내림차순 정렬
        # {곡의 인덱스:재생 수} 딕셔너리 생성
        genre_idx = [i for i in range(len(genres)) if k == genres[i]]   # 해당 장르 인덱스 기록하는 리스트 생성
        genre_play = [plays[p] for p in genre_idx]  # 그 장르 곡들의 재생 수 기록하는 리스트 생성
        play_list = dict(zip(genre_idx, genre_play))
        play_list = sorted(play_list.items(), key=(lambda x:x[1]), reverse=True)
        
        # 2개씩 answer 리스트에 넣기
        answer.append(play_list[0][0])  # 하나는 무조건 존재
        if len(play_list) >= 2:
            answer.append(play_list[1][0])
        
    return answer

 

 

 

 

 

- 문제에서 조건, 요구하는 바를 주석으로 먼저 정리!!!

- 모든 테스트 케이스가 커버 가능한 알고리즘 -> 테스트 케이스도 주석으로 작성해가며 문제 풀기!!!!