프로그래머스 순위검색 파이썬

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

 

2. 풀이

- dic를 사용하기. key는 고정된 값이고 value는 추가하거나 바꿀 수 있는 값이다.

여기에서는 4가지의 값(언어, 위치, 경력, 음식)으로 고정된 key를 만들 수 있고 score가 다양할 수 있으니 value로 넣는 아이디어가 필요하다.

- '-'가 들어가는 경우의 수가 그렇게 만지 않으니 직접 구현하는 것도 가능

- 이분탐색(bisect_left)을 쓰기 위해 dic를 정렬하는 것. (효율성)

- dictionary search할때는 항상 dic에 있는 지 확인하고 있는 경우에만 탐색한다. 중요중요!

 

3. 구현

from bisect import bisect_left 
def make_key(lis):
    l = lis[0]
    p = lis[1]
    c = lis[2]
    f = lis[3]
    
    tmp=[
        [l,p,c,f],
        ["-",p,c,f],
        [l,"-",c,f],
        [l,p,"-",f],
        [l,p,c,"-"],
        ["-","-",c,f],
        ["-",p,"-",f],
        ["-",p,c,"-"],
        [l,"-","-",f],
        [l,"-",c,"-"],
        [l,p,"-","-"],
        ["-","-","-",f],
        ["-","-",c,"-"],
        ["-",p,"-","-"],
        [l,"-","-","-"],
        ["-","-","-","-"]
    ]
    return tmp
    

def solution(info, query):
    answer = []
    
    lang=['cpp', 'java', 'python']
    position=['backend', 'frontend']
    career=['junior', 'senior']
    food=['chicken', 'pizza']
    
    dic = dict()
    for i in info:
        lis = i.split()
        score = lis[-1]
        key_lis = make_key(lis[:-1])
        for k in key_lis:
            key = "".join(k)
            if key not in dic:
                dic[key]=[]
            dic[key].append(int(score))
    for key in dic.keys():
        dic[key] = sorted(dic[key])
    
    for q in query:
        q = q.replace('and', '')
        lis = q.split()
        key="".join(lis[:-1])
        score = lis[-1]
        if key in dic.keys():
            answer.append(len(dic[key])-bisect_left(dic[key], int(score)))
        else:
            answer.append(0)
    return answer