Programmers. 순위 검색

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 순위 검색

문제 풀이

4차원 배열로 정확성은 통과했으나 효율성은 통과하지 못했다. 라이트업을 보니 와일드카득 ㅏ들어갈 모든 경우의 수에 대해 hash키를 만들고 모조리 16가지의 키에 저장하여 키 조회 때마다 정렬된 배열을 불러와 이분탐색을 사용해 시간복잡도를 줄여야 했다. 너무 신박한 풀이라 애초에 혼자서는 해결할 수 없었을 것이다.

• 각 기준에 와일드카드를 넣을 지 결정하는 16가지경우의 수에 대해 삽입합수 정의
• 사전에 모든 키에 대해 조회하여 정렬 수행
• 각 쿼리에 대해 키를 조회하여 lower bound를 찾고 값 저장

python 코드

from collections import defaultdict
from itertools import combinations
from bisect import bisect_left


def solution(info, query):
    tmp = [[0], [1], [2], [3]]
    for i in range(2, 5):
        s = [j for j in range(4)]
        com = combinations(s, i)
        for co in list(com):
            tmp.append(list(co))

    def make_case(info_l, score, tmp):
        user_dict["".join(info_l)].append(score)
        for c in tmp:
            buf = info_l.copy()
            for x in c:
                buf[x] = "-"
            key = "".join(buf)
            user_dict[key].append(score)
    user_dict = defaultdict(list)
    for user in info:
        info_list = user.split()
        info_l = info_list[:-1]
        score = int(info_list[-1])
        make_case(info_l, score, tmp)
    for key in list(user_dict):
        user_dict[key].sort()
    answer = []
    for que in query:
        que_l = que.split()
        q_l = [que_l[0], que_l[2], que_l[4], que_l[6]]
        score = int(que_l[7])
        key = "".join(q_l)
        value_list = user_dict[key]
        answer.append(len(value_list) - bisect_left(value_list, score))
    return answer