[프로그래머스] 파이썬 - 순위 검색 (KAKKO)

문제

풀이

첫번째 코드 - 시간초과

from itertools import product

def check_query(language, job_type, ex_level, soulfood,score):
    global information
    cnt = 0
    a = []
    b = []
    c = []
    d = []
    
    if language == "-":
        a = ["cpp", "java", "python"]
    else:
        a.append(language)
    if job_type == "-":
        b = ["backend", "frontend"]
    else:
        b.append(job_type)
    if ex_level == "-":
        c = ["junior", "senior"]
    else:
        c.append(ex_level)
    if soulfood == "-":
        d = ["chicken", "pizza"]
    else:
        d.append(soulfood)
    
    # 조건의 모든 경우의 수를 key값으로 가지는 dictionary information 선언
    for i in list(product(a,b,c,d)):
        for j in information[" ".join(i)]:
            if j != 0 and j >= int(score):
                cnt+= 1
    return cnt

def solution(info, query):
    answer = []
    global information
    information = {}
    
    language = ["cpp", "java", "python"]
    job_type = ["backend", "frontend"]
    ex_level = ["junior", "senior"]
    soulfood = ["chicken", "pizza"]
    
    # 조건의 모든 경우의 수를 key값으로 가지는 dictionary information 선언
    for i in list(product(language, job_type, ex_level, soulfood)):
        key = " ".join(i)
        information[key] = []
    
    # info 배열에 있는 값들 information에 채우기
    for i in info:
        lst = i.split()
        information[" ".join(lst[:4])].append(int(lst[-1]))

    # query 검사
    for i in query:
        query_language, query_job_type, query_ex_level, last = i.split(" and ")
        query_soulfood, score = last.split()  
        
        cnt = 0
        cnt += check_query(query_language, query_job_type, query_ex_level,query_soulfood,score)
        answer.append(cnt)
        
    return answer

 

주어진 언어와 직업과 경력, 선호 음식의 개수가 각각 3,2,2,2개로 작은 숫자이므로 모든 경우의 수를 구해 딕셔너리에 key값으로 두었다.

그리고 info의 정보를 통해 각 지원자의 점수를 value값으로 두었다.

 

이렇게 만들어진 Information 딕셔너리를 통해 query를 탐색했는데, 시간초과가 나왔다.

 

두번째 코드  - 시간초과

from itertools import product
from collections import defaultdict

def solution(info, query):
    answer = []
    global information
    information = defaultdict(list)
    
    # info 배열에 있는 값들 information에 채우기
    for i in info:
        lst = i.split()
        keys = lst[:4]
        value = int(lst[-1])
        
        for j in product([keys[0], '-'],[keys[1], '-'],[keys[2], '-'],[keys[3], '-']):
            information[" ".join(j)].append(value)

    # query 검사
    for i in query:
        query_language, query_job_type, query_ex_level, last = i.split(" and ")
        query_soulfood, score = last.split()  
        
        key = query_language+" "+ query_job_type+" "+ query_ex_level+" "+query_soulfood
        cnt = 0
        
        for j in information[key]:
            if j>=int(score):
                cnt+=1
        answer.append(cnt)
        
    return answer

 

첫번째 코드와 달라진 점은 다음과 같다.

 

1. defaultdict 사용하여 간결한 코드 작성

2. "-"가 포함된 모든 경우의 수를 탐색하여 작성

 

그래도 시간초과가 났다.

애초에 query의 길이가 길어 그런 것 같았다.

query 탐색 자체에서 시간복잡도를 줄여야 할 것 같았다.

 

최종 코드 

from itertools import product
from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    global information
    information = defaultdict(list)
    
    # info 배열에 있는 값들 information에 채우기
    for i in info:
        lst = i.split()
        keys = lst[:4]
        value = int(lst[-1])
        
        for j in product([keys[0], '-'],[keys[1], '-'],[keys[2], '-'],[keys[3], '-']):
            information[" ".join(j)].append(value)
    
    # dict안의 조합들을 점수순으로 정렬
    for i in information:
        information[i].sort()  

    # query 검사
    for i in query:
        query_language, query_job_type, query_ex_level, last = i.split(" and ")
        query_soulfood, score = last.split()  
        
        key = query_language+" "+ query_job_type+" "+ query_ex_level+" "+query_soulfood
        cnt = 0
        
        # bisect_left로 정렬되어있는 딕셔너리 value값에 현재 score가 들어갈 위치 찾기
        score_position = bisect_left(information[key],int(score))
        
        answer.append(len(information[key]) - score_position)
        
    return answer

 

딕셔너리 내의 각 조합에 따른 score value 배열을 미리 정렬시켜둔뒤

bisect_left를 통해 score가  score value 배열에 들어갈 위치를 구해주었다.

이를 사용하면 시간복잡도가 O(logN)으로 줄어드므로 시간초과가 나지않았다.

 

 

오늘 배운 내용

Defaultdict

파이썬의 collections 모듈에 속해있다.

쓰임새는 일반 딕셔너리와 비슷하지만 defaultdict는 만들 때 value의 타입을 지정해준다.

default_dict = defaultdict(list)

 

이러면 defaultdict의 모든 key값에 대해서 기본적으로 해당 타입의 기본 값을 생성해준다.

 

첫 번째 코드에서 내가 아래처럼 썼는데, 이런 과정을 생략할 수 있다.

for i in list(product(language, job_type, ex_level, soulfood)):
    key = " ".join(i)
    information[key] = []

 

장점으로는 

1. 코드가 간결해진다.

2. 기본 딕셔너리는 존재하지 않는 key값에 접근하면 오류가 나는데, defaultdict를 사용하면 에러가 나지 않는다.

    따라서 key값이 존재하는지 확인하는 코드도 줄일 수 있다.

 

 

프로그래머스