[프로그래머스 고득점 kit] 해시

del dict_obj[key]
만약 딕셔너리에 key가 없다면 keyError가 발생
pop(key[,default])
key 값에 해당하는 value를 리턴. key가 없다면 두번째 파라미터인 default를 리턴.
(만약 default 설정하지 않았을 시엔 keyError가 발생)

순회 (iterate)

key로만 순회하기
for key in dictionary:
key, value 동시 순회하기 (items() 사용)
for key, value in dictionary.items():

기타 메소드

특정 key가 딕셔너리에 있는지 조회할 때 : in
key만 뽑아낼 때 : keys()
value만 뽑아낼 때 : values()

딕셔너리 정렬

key 기준으로 정렬
sorted(dictionary.items()) : 오름차순 정렬, 정렬된 딕셔너리를 리스트 형으로 반환
- dictionary.keys() 로 정렬 : 정렬된 Key 값만 리스트로 반환
- dictionary.items()로 정렬 : 튜플(Tuple) 형태로 Key값 기준으로 정렬된 리스트가 반환
value 기준으로 정렬하기
sorted 함수에 key 옵션을 lambda 함수를 이용하여 value값으로 지정
sorted(dictionary.items(), key=lambda item : item[1])
(item[0] : key, item[1] : value)

프로그래머스 고득점 kit 문제

Lv 1. 폰켓몬

딕셔너리에 폰켓몬 이름을 기준으로 값을 넣어준다. 딕셔너리의 key값의 개수가 폰켓몬의 총 종류 수이므로 n/2와 key값 길이를 비교하여 더 작은 값을 리턴하면 된다.

def solution(nums):
    answer = 0
    d = {}
    for item in nums:
        if item in d:
            d[item] += 1
        else:
            d[item] = 1
    
    if len(d.keys()) > (len(nums) / 2):
        answer = len(nums) / 2
    else:
        answer = len(d.keys())
    return answer

dict.fromkeys(key값, value) 메서드 : key값으로 지정할 리스트를 넘겨준 뒤 value로 지정할 값을 넘겨주면 딕셔너리를 생성하여 반환
참가자 이름을 기준으로 딕셔너리에 값을 넣어준다. 완주자 배열을 돌면서 딕셔너리에서 값을 빼주는데 (시간복잡도 O(1)) 만약 값이 0이면 해당 키 값을 없애준다.
완주자와 참가자는 1명 차이가 나므로 최종적으로 딕셔너리에 남아있는 키 값이 완주하지 못한 선수의 이름이다.

def solution(participant, completion):
    answer = ''
    
    d = dict.fromkeys(participant, 0)
    
    for p in participant:
        d[p] += 1
    
    for c in completion:
        d[c] -= 1
        if d[c] == 0:
            del d[c]
    
    for i in d.keys():
        answer = i
    return answer

Lv 2. 전화번호 목록

엄청나게 삽질했던 문제. 이틀을 붙잡았다... 그리고 전화번호가 0~9 사이의 숫자로 시작할 수 있음을 잊고 풀어서 테케에서도 우수수 틀렸다.

딕셔너리에 싹 넣고 리스트 슬라이싱을 통해 비교 : 당연히 시간초과
딕셔너리에 0 ~ 9 사이의 키 값을 기준으로 데이터를 넣고 리스트 슬라이싱을 통해 비교 : 시간 초과 (효율성 3,4번)
2번 풀이에 길이순 정렬을 위해 sort() 추가 : 시간 초과 (효율성 3,4번)

# 3. 효율성 3,4번 테케에서 시간초과 난 코드 (이렇게 풀면 안된다...)
def solution(phone_book):
    answer = True
    d = { str(i):[] for i in range(10) }
    phone_book.sort()
    for phone in phone_book:
        if len(d[phone[0]]) == 0:
            d[phone[0]].append(phone)
        else:
            for item in d[phone[0]]:
                for i in range(min(len(item), len(phone))):
                    if item[i] != phone[i]:
                        break
                    if i == (min(len(item), len(phone)) - 1):
                        return False
            d[phone[0]].append(phone)
    return answer

(정답) sort()를 해주고 나면 굳이 다 살펴볼 필요가 없음을 캐치해야 한다!!!!

['1', '11', '112', '345']

데이터를 정렬한 뒤에는 이렇게 생겼을 것이다. 그러면 접두사가 될 수 있는 요소는 바로 이전에 등장한 데이터이다. 굳이 다 살펴볼 필요가 없는 것!!

# 정답 코드
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][:len(phone_book[i])]:
            return False
    return answer

Lv 2. 의상

조합을 사용해서 풀이 -> 테케 1번만 시간초과 (아마도 n=30인듯)

# 시간초과난 코드
import math
from itertools import combinations
def solution(clothes):
    answer = 0
    # 조합으로 뽑아내면 될 듯
    data = {}
    for item in clothes:
        name, kind = item
        if kind in data:
            data[kind] += 1
        else:
            data[kind] = 1
    
    case = []
    for i in range(1, len(data.keys())+1):
        case += list(combinations(list(data.keys()), i))
    
    for item in case:
        result = 1
        for i in range(len(item)):
            result *= (math.comb(data[item[i]], 1))
        answer += result
    
    return answer

한개씩 경우를 곱해가면서 데이터를 추가하는 방식... 시간초과 ㅠ

# 나름 괜찮다 생각했건만 시간초과... ㅠㅠ
def solution(clothes):
    answer = 0
    data = {}
    for item in clothes:
        name, kind = item
        if kind in data:
            data[kind] += 1
        else:
            data[kind] = 1
    
    
    case = []
    
    
    for key in data:
        if len(case) == 0:
            case.append(data[key])
        else:
            origin_length = len(case)
            for i in range(origin_length):
                case.append(case[i] * data[key])
            case.append(data[key])
            
    answer = sum(case)
    
    return answer

(정답) 힌트를 보고 풀었다. 아무것도 안 입는 경우만 제외해주면 되는 간단한 문제였다... 고등학교 때 확률과 통계 약했는데 그게 여기서 티가 날 줄이야
우선, 착용할 수 있는 모든 경우의 수를 구하려면 각 카테고리 별 요소의 수를 곱해야 한다. 하지만 아무것도 안 입는 경우를 고려해야 하므로 +1 해준다. 그러고 아무것도 입지 않았을 때의 경우만 빼주면 된다.

def solution(clothes):
    answer = 1
    data = {}
    for item in clothes:
        name, kind = item
        if kind in data:
            data[kind] += 1
        else:
            data[kind] = 1
    
    for key,value in data.items():
        answer *= (value + 1)
    
    answer -= 1
    
    return answer

Lv 3. 베스트 앨범

딕셔너리 d에 key로는 장르명, value로는 (재생횟수, 고유인덱스) 값을 부여했다.
딕셔너리 count에 key로는 장르명, value로는 총 재생횟수의 총합을 구했다. 처음 reduce함수를 사용해봤다!

reduce 함수

reduce 함수는 파이썬3부터는 내장함수가 아니어 import를 해줘야 한다.

from functools import reduce

reduce 함수는 (집계함수, 순회가능한 데이터[, 초기값])을 갖는다. 따라서 집계함수를 위해 lambda를 사용했다.

조건에 맞춰서 데이터를 뽑으면 끝~!

# 한방에 통과해서 조금 눈물이 났다 기쁨의 눈물이...
from functools import reduce
def solution(genres, plays):
    answer = []
    
    d = {}
    for i in range(len(genres)):
        if genres[i] in d:
            d[genres[i]].append((plays[i], i))
        else:
            d[genres[i]] = [(plays[i], i)]
    
    count = {}
    for key in d.keys():
        d[key].sort(reverse=True, key=lambda x: (x[0], -x[1]))
        # 재생횟수만 누적합
        count[key] = reduce(lambda acc, cur: acc + cur[0], d[key], 0) 
    
    # [('장르명', 재생횟수 총합)]
    sort_count = sorted(count.items(), key=lambda item: -item[1] ) 
    
    for item in sort_count:
        key = item[0]
        
        if len(d[key]) == 1:
            answer.append(d[key][0][1])
        else:
            answer.append(d[key][0][1])
            answer.append(d[key][1][1])
            
    return answer

thousand_yj

함께 일하고 싶은 개발자가 되기 위해 노력합니다. 코딩테스트 관련 공부 및 이야기는 티스토리에도 업로드되어 있습니다.

이전 포스트

파이썬 자료형 공부 - dict, defaultdict, set

다음 포스트

[프로그래머스 고득점 kit] 해시

코딩테스트

해시

딕셔너리와 리스트의 시간 복잡도 차이

딕셔너리 사용하기

딕셔너리 생성

get

set

delete