[Python] 순위 검색

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

---

풀이

처음에는 단순히 for문을 이용해서 풀었다가 정확성은 통과했지만 효율성 테스트에서 통과를 못하여 어떻게 하면 시간을 줄이지라는 고민을하다 결국 검색을 통해서 이분탐색을 사용하면 해결이 가능하다는것을 알게되었습니다.

이분탐색을 하기전 info에서 입력받은 값을 와일드카드인 '-'를 포함시킬 수 있게 조합을 사용해서 만들어 그 값을 딕셔너리에 Key로 추가하고 Value는 점수를 넣게 하였습니다

이때, 만약 그 키 값이 이미 딕셔너리에 들어있다면 점수비교를 위해 Value 뒤에 점수를 추가해야하므로 리스트 자료형을 사용했습니다.

그 다음 딕셔너리의 각 키마다의 점수 즉, 벨류를 오름차순으로 정렬하였습니다.

마지막으로 query를 하나씩 읽어오면서 점수와 조건을 분리시키고 조건을 미리 만들어둔 딕셔너리의 키값과 비교하여 이미 있다면 해당 키의 위치에 있는 벨류 즉, 점수들에서 query의 점수보다 크거나 같은 값을 찾기위해 이분탐색을 사용하여 인덱스를 찾아 해당 키의 value의 총 개수와 빼어 해당 query의 조건에 부합하는 인원의 수를 구하여 해결했습니다.

---

코드

from itertools import combinations
from bisect import bisect_left


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

    conditions_dict = {}
    for i in info:
        i_list = i.split()
        # 조건들과 점수를 따로 나눔
        conditions = i_list[:-1]
        score = int(i_list[-1])

        combi_list = [0, 1, 2, 3]
        for cnt in range(5):  # 조건들에 대해 조합을 이용해서
            wildcard_idx_list = list(combinations(combi_list, cnt))
            for wildcard_idx in wildcard_idx_list:
                conditions_list = conditions.copy()
                for idx in wildcard_idx:
                    conditions_list[idx] = "-"

                conditions_str = "".join(conditions_list)

                if conditions_str in conditions_dict:
                    conditions_dict[conditions_str].append(score)
                else:
                    # 점수를 계속 추가하기위해 리스트를 딕셔너리 value에 추가
                    conditions_dict[conditions_str] = [score]

    for c in conditions_dict.values():
        c.sort()

    for q in query:
        q_list = [i for i in q.split(" ") if i != "and"]
        q_condition = "".join(q_list[:-1])
        q_score = int(q_list[-1])

        if q_condition in conditions_dict:
            scores = conditions_dict[q_condition]

            if len(scores) > 0:
                st = bisect_left(scores, q_score)
                answer.append(len(conditions_dict[q_condition]) - st)
        else:
            answer.append(0)

    return answer

---

pyo7410/Algorithm