[Python/프로그래머스]순위검색_(KaKao)_[구현,bisect(이분탐색)]

 

 

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

프로그래머스

 

 

 

 

으렵다. 레벨 2인데 이러면 어떡하지..ㅋㅋㅋㅋ

 

 

 

풀이과정 : 

 

1. info를 공백을 기준으로 나눈다.
2. 점수와 나머지들을 각각 value, key로 구분한다.
3. key로 만들 수 있는 모든 조합을 combination을 이용해 만든다. 
4. info_dict에 이 조합을 가진 지원자가 있음을 점수를 저장하면서 알려준다.
5. 저장한 점수들은 이분탐색을 이용할 것이므로 정렬해준다.
6. 쿼리를 돌면서 점수와 나머지값들을 구분해준다.
7. and와 - 를 제거해준다.
8. 만약 나머지값(key)가 info_dict에 있다면 저장되어있는 점수들을 확인하여 이분탐색한다.
9. bisect_lefft를 이용해 왼쪽 값을 반환받고 이를 전체 길이에서 빼주면 명수가 나온다.
10. answer에 붙여넣는다. 

 

 

 

배운것 

 

 

1. 리스트에서 특정 문자를 없애고 싶을 때 

while '특정 문자' in 리스트 :

      리스트.remove('특정 문자')

 

 

 

2. 이분탐색 - bisect 

파이썬에는 이분탐색을 위한 라이브러리가 있다. 

bisect인데 동일한 값에 대해 어떻게 대처할건지에 따라 

bisect_left, bisect_right이 있다. 

https://folivora.tistory.com/83

[Python] 이진 검색 (Binary Search): bisect_left와 bisect_right

참고 하세용

 

 

 

 

 

여기서는 해당 점수 이상인 사람의 수를 세면 되니까 

동일한 점수의 경우 왼쪽에 위치하여 그 인덱스를 받고 전체 길이에서 빼주면 된다~!

 

 

 

 

 

 

 

 

 

코드 : 

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    answer = []
    info_dict = {}

    for i in range(len(info)):
        infol = info[i].split()  # info안의 문자열을 공백을 기준으로 분리
        mykey = infol[:-1]  # info의 점수제외부분을 key로 분류
        myval = infol[-1]  # info의 점수부분을 value로 분류

        for j in range(5):  # key들로 만들 수 있는 모든 조합 생성
            for c in combinations(mykey, j):
                tmp = ''.join(c)
                if tmp in info_dict:
                    info_dict[tmp].append(int(myval))  # 그 조합의 key값에 점수 추가
                else:
                    info_dict[tmp] = [int(myval)]
	# dict안의 조합들을 점수순으로 정렬
    # 이분탐색을 하기 위해서 정렬
    for k in info_dict:
        info_dict[k].sort()  

    for qu in query:  # query도 마찬가지로 key와 value로 분리
        myqu = qu.split()
        qu_key = myqu[:-1]
        qu_val = myqu[-1]

        while 'and' in qu_key:  # and 제거
            qu_key.remove('and')
        while '-' in qu_key:  # - 제거
            qu_key.remove('-')
        qu_key = ''.join(qu_key)  # dict의 key처럼 문자열로 변경

        if qu_key in info_dict:  # query의 key가 info_dict의 key로 존재하면
            scores = info_dict[qu_key]

            if scores:  # score리스트에 값이 존재하면
                enter = bisect_left(scores, int(qu_val))

                answer.append(len(scores) - enter)
        else:
            answer.append(0)

    return answer

 

 

 

 

 

 

 

참고 블로그 : 

https://hongcoding.tistory.com/56

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

🐾 20221014