프로그래머스 21kakao_blind 순위검색(python)

이 글은 Tistory에서 이전된 포스팅입니다. 원본은 여기에서 확인할 수 있습니다.

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

from bisect import bisect_left

def solution(info, query):
    a = {"java":"0", "cpp":"1", "python":"2"}
    b = {"backend":"0", "frontend":"1"}
    c = {"junior":"0", "senior":"1"}
    d = {"chicken":"0", "pizza":"1"}
    
    results = []
    for i in info:
        lang, posi, car, food, score = i.split(" ")
        results.append([a[lang], b[posi], c[car], d[food], int(score)])
    
    r = {}
    for result in results:
        _d = "".join(result[:4])
        if (r.get(_d)):
            r[_d].append(result[4])
        else:
            r[_d] = [result[4]];

    answer = []
    s_dp = {}
    for __i in r.keys():
        s_dp[__i] = False
        
    for q in query:
        lang, posi, car, f = q.split(" and ")
        food, score = f.split(" ")
        u1 = []; u2 = []; u3 = []; u4 = []
        if (lang == "-"):
            u1.append("0"); u1.append("1"); u1.append("2");
        else:
            u1.append(a[lang])
        
        if (posi == "-"):
            u2.append("0"); u2.append("1");
        else:
            u2.append(b[posi])
        
        if (car == "-"):
            u3.append("0"); u3.append("1");
        else:
            u3.append(c[car])
        
        if (food == "-"):
            u4.append("0"); u4.append("1");
        else:
            u4.append(d[food])
        
        count = 0
        for _u1 in u1:
            for _u2 in u2:
                for _u3 in u3:
                    for _u4 in u4:
                        s = _u1 +_u2 + _u3 + _u4
                        if r.get(s):
                            arr = r[s]
                            if not s_dp[s]:
                                arr.sort()
                                s_dp[s] = True
                            f = bisect_left(arr,int(score))
                            count += len(arr) - f
        answer.append(count)
    return answer

접근

java backend junior pizza = “0001”

python frontend senior chicken = “2110”

info를 순회하면서 다음과 같은 dictionary를 만든다.

{“0001” : [150, 200], “2110” : [80] …. }

query를 순회하며 문자열( ex) “0001” )로 치환하고

해당 문자열을 key로 dictionary에 접근하여 정렬된 점수 리스트에서 이진 탐색을 하고 높거나 같은 점수를 count 한다.

“0-01”은 [“0001”, “0101”] 과 같이 가능한 모든 경우를 만든다.

key에 해당하는 스코어 리스트는 최초 조회시 sort 하고 dp를 적용해 두 번부터는 sort를 적용하지 않는다.