해시

1. 폰켓몬

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

문제 풀이 접근 설계

• Hash Set 만들기
• if Hash Set 길이 > 가질 수 있는 최대 갯수 return 가질 수 있는 최대 갯수
• return Hash Set 길이
  

내 풀이

def solution(nums):

    pocketmon_set = set(nums)
    
    if (len(pocketmon_set)) > (len(nums) // 2):
        return len(nums) // 2
        
    return len(pocketmon_set)

더 간단한 풀이

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

2. 완주 하지 못한 선수 (20분 소요)

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

문제 풀이 접근 설계

• 딕셔너리 Set 생성
• participant에 속하면 카운트 1 증가
• completion에 속하면 카운트 1 감소
• value가 1인 키 찾아 return

from collections import defaultdict
def solution(participant, completion):
    answer = defaultdict(int)
    
    for index, value in enumerate(completion):
        answer[completion[index]] -= 1
        answer[participant[index]] += 1
    answer[participant[-1]] += 1
    # sort로 찾는 방법
    # return sorted(answer.items(), key=lambda x: x[1])[-1][0]
    # 값으로 찾는 방법
    result = [key for key, value in answer.items() if value == 1]
    return result[0]

더 간단한 풀이
Dict 사용할 때는 Collections를 쓰자!
list로 converting 하는 것 필수!

from collections import Counter
def solution(participant, completion):
    answer = Counter(participant) - Counter(completion)
    
    return list(answer.keys())[0]

3. 전화번호 목록 (30분 소요)

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

문제 풀이 접근 설계

• Sort
• O(N) : 전화번호 20자 제한
• for문 한바퀴 돌면서 바로 오른쪽 문자열 비교 (i, i+1)
• 현재 비교하는 length와 문자열 같으면 return false

내 풀이

def solution(phone_book):
    answer = True
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][0: len(phone_book[i])]:
            return False
    return True

시간 초과 풀이

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        length = len(phone_book[i])
        for j in range(i+1, len(phone_book)):
            if len(set(phone_book[i]) - set(phone_book[j][:length])) == 0:
                if phone_book[i] == phone_book[j][:length]:
                    return False
    return True

정석 풀이 (해시 사용)
해시가 진짜 빠르긴 하구먼 ! 비교 할때는 해시부터 고려해보자

from collections import defaultdict

def solution(phone_book):
    answer = True
    hash = defaultdict(int)
    for phone_number in phone_book:
        hash[phone_number] += 1
    for phone_number in phone_book:
        temp = ""
        for phone in phone_number:
            temp += phone
            if temp in hash and temp != phone_number:
                return False
    return answer

4. 위장 (4분 소요)

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

문제 풀이 접근 설계

• 의상의 종류로 해시 키 잡고 갯수 count
• 해시 for문 돌면서 answer *= (의상의 종류 + 1)
• 아무것도 없을 경우를 위해 answer에서 1 빼기

내 풀이

from collections import defaultdict
def solution(clothes):
    answer = 1
    hash = defaultdict(int)
    
    for cloth in clothes:
        hash[cloth[1]] += 1
    for cloth in hash:
        answer *= (hash[cloth] + 1)
    return answer - 1

5. 베스트 앨범(30분 소요)

문제 풀이 접근 설계

• hash count로 장르별 플레이수 세기
• hash count sort (플레이수 많은 순서대로)
• hash value (재생수, 고유 번호) 재생 수별로 sort
• 2개씩만 뽑아서 answer list에 추가

내 풀이

from collections import defaultdict
def solution(genres, plays):
    answer = []
    hash_count, hash_value  = defaultdict(int), defaultdict(list)
    for index, value in enumerate(genres):
        hash_count[value] += plays[index]
        hash_value[value].append([plays[index], index])

    hash_count = sorted(hash_count.items(), reverse = True, key=lambda x: x[1])
    for value in hash_count:
        temp = sorted(hash_value[value[0]], reverse = True, key=lambda x: x[0])
        try: 
            answer.append(temp[0][1])
        except: continue
        try: 
            answer.append(temp[1][1])
        except: pass
    
    return answer