프로그래머스 - 순위검색 python

Jamwon·2021년 8월 24일
0

알고리즘

목록 보기
16/18
post-thumbnail

문제 링크

푸는 법

여러 경우의 수 중에서 주어진 score이상의 조건문에 부합하는 info의 수를 count하는 것이다.

query문중에 '-' 가 포함되어있는데 '-'는 조건문에 포함되지않는다.

따라서 "java backend junior pizza 150" 라는 info가 있으면 개발 언어, 직군, 경력 소울 푸드는 있거나 없을수도 있는 즉 2^4개로 16개의 다른 query에 부합한다고 볼 수 있다.

따라서 각 info마다 16개의 다른 info문을 만들어서 dictionary에 넣어놓는다. key값은 -를 없엔 string문이고 value값은 list안에 점수를 추가한다.

그리고 Lower bound를 구현하여 query와 dictionary와 value가 같은것 중에서 score가 같거나 높은 원소의 갯수를dictionary의 value에서 구한다.

parsing

기존의 데이터를 다른 형태로 가공하는 것.

이 문제에서는 info를 파싱해서 -를 삭제한 붙어있는 문자열 방식으로 파싱!

defaultdict()

딕셔너리를 만드는 dict클래스의 서브 클래스

form collections import defaultdict 로 사용가능

인자로 주어진 객체의 기본값을 딕셔너리값의 초기값으로 지정가능

list_dict = defaultdict(list)

위와같이 설정하면 값을 지정하지 않은 키는 빈 list로([]) 지정된다.

Lower bound

'정렬' 된 배열에서 찾고자 하는 값 이상이 처음으로 나타나는 위치를 찾을때 사용된다.

같은 원소가 여러개 있더라도 상관이없다는 장점이있다.

이분 탐색 방법을 응용

list =[1,3,3,5,7,7,8] 의 숫자 배열이 있다고 할때 7이상의 위치를 찾으려고 할때

구간이 [0, len(list)] 이다.
구간의 중간위치를 m이라고 하면
list[m-1] <7 이면서 list[m] >= 7를 만족하는 최소 m를 찾으면 된다!

리스트를 탐색할때 7과 같거나 큰수가 나오는 첫 위치가 바로 lower bound이다.

코드

from itertools import combinations
from collections import defaultdict


def solution(info, query):
    answer = []
    info_dict = defaultdict(list)

    for infos in info:
        temp = infos.split(" ")
        key = temp[:-1]
        score = int(temp[-1])

        for i in range(5):
            combi = list(combinations(key, i))
            for c in combi:
                temp_key = ''.join(c)
                info_dict[temp_key].append(score)
    for key in info_dict.keys():
        info_dict[key].sort()
    print(info_dict)

    for querys in query:
        querys = querys.split(" ")
        query_key = querys[:-1]
        query_score = int(querys[-1])
        # print(query_key)
        ## and 는 최대 3개 까지 있다.
        for _ in range(3):
            query_key.remove("and")
        while "-" in query_key:
            query_key.remove("-")

        ##하나의 string으로 만든다.
        query_key = ''.join(query_key)

        if query_key in info_dict:
            scoreList = info_dict[query_key]
            # print(scoreList)
            if len(scoreList) > 0:
                left, right = 0, len(scoreList)
                while left < right:
                    mid = (left + right) // 2
                    if scoreList[mid] >= query_score:
                        right = mid
                    else:
                        left = mid + 1
                answer.append(len(scoreList) - left)
        else:
            answer.append(0)
    # print(answer)
    return answer

분명 프로그래머스 2레밸 문제라는데 어렵다..원래 2레밸이 이렇게 어려웠나 싶다...혼자 힘으로 못푼문제

combination이 많이쓰이는거 같도 lower bound도 중요하다.

파싱도 중요.. 중요한 요소가 엄청 많은 문제!!

복습 꼭많이하자

profile
한걸음씩 위로 자유롭게

0개의 댓글