[Python] 프로그래머스 알고리즘 고득점 Kit ✅ 해시 (~ing)

[Level 1] 폰켓몬

def solution(nums):
    answer = 0
    
    # 폰켓몬 종류 개수
    num = len(list(set(nums)))
    
    # 뽑아야 하는 폰켓몬 개수
    num_pick = int(len(nums)/2)
    
    # 폰켓몬 종류가 뽑아야 하는 폰켓몬 개수 보다 많으면 그냥 폰켓몬 종류 개수
    # 왜냐하면, 우리는 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아서 폰켓몬 종류 번호의 개수를 찾는 것
    # 쉽게 말하면, 2개 뽑는데 1, 2, 3이라는 종류가 있다면 어떤 조합을 해도 1, 2 / 2, 3처럼 최대 종류 개수가 2개임
    if num > num_pick: answer = num_pick
    elif num == num_pick: answer = num_pick
    # 그런데 3개 뽑는데 종류가 2개야. 그러면 어쨋든 최대로 조합될 수 있는 최대 종류 개수는 강제로 2개가 되는거지
    else:
        answer = num
    
    return answer

 

[Level 1] 완주하지 못한 선수

remove 함수는 리스트 일부 값을 지워주는 것 (remove 안에 값을 정확히 넣어주어야 함)

주의해야 할 점은 해당 값과 똑같은 가장 첫 번째 값만 지워준다는 것!

 

초기 코드는 아래와 같다.

def solution(participant, completion):
    answer = ''
    
    for i in range(len(participant)-1):
    
        # 완주한 사람 (completion에서 값 제거) -> 동명이인 처리
        if participant[i] in completion:
            completion.remove(participant[i])
            
        # 완주하지 못한 사람
        else:
            answer = participant[i]
    
    return answer

 

그런데 효율성 오류가 났음. 수정!

def solution(participant, completion):
    answer = ''
    
    # 효율성 테스트로 인해 sort 후 진행
    participant.sort()
    completion.sort()
    
    for i in range(len(participant)-1): # completion이 값이 하나 적으니까
        if participant[i] != completion[i]:
            answer = participant[i]
            return answer # 어차피 완주 못 한 사람은 1명이니까 return 해도 됨
    
    # 마지막에 완주하지 못한 사람이 있을 경우 -1 인덱스로 return
    answer = participant[-1]
    return answer

 

[Level 2] 전화번호 목록

초기 코드는 아래와 같다.

def solution(phone_book):
    # 정렬 후 진행 (시간 단축을 위해)
    phone_book.sort()
    
    for i in range(len(phone_book)):
        for j in range(1, len(phone_book)):
            # 문자열 길이가 같거나 더 짧으면 pass
            if len(phone_book[i]) < len(phone_book[j]):
                # 접두어가 같으면 answer 값 변경 후 break
                if phone_book[i] == phone_book[j][:len(phone_book[i])]:
                    return False
    return True

 

효율성 테스트 3번, 4번을 통과하지 못했다. 수정한 코드는 다음과 같다. (for 반복문을 줄임)

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

 

참고한 해시 함수의 정석적인 코드는 아래와 같다.

def solution(phone_book): 

    # 1.Hash map생성
    hash_map = {} 
    for nums in phone_book: 
        hash_map[nums] = 1 
    
    # 2.접두어가 Hash map에 존재하는지 찾기 
    for nums in phone_book: 
        arr = "" 
        for num in nums: 
            arr += num
    
            # 3. 본인 자체일 경우는 제외
            if arr in hash_map and arr != nums:       
                return False 
                
    return True

 

[Level 2] 의상

못 풀어서 아래 참고 링크로 달아둔 분의 코드를 참고했다.

def solution(clothes):
    # 각 종류별 가진 의상을 저장 (종류:[이름, 이름, ...])
    closet = {} 
    for name, kind in clothes:
        if kind in closet.keys():
            closet[kind] += [name]
        else:
            closet[kind] = [name]
    
    # A의 종류가 N개, B의 종류가 M개 일 때 가능한 모든 경우의 수 (N+1)(M+1)
    answer = 1
    for _, value in closet.items():
        answer *= (len(value) + 1)
        
    return answer -1

 

프로그래머스 | 의상 [파이썬 python]

 

[Level 3] 베스트 앨범

ing