2021 카카오 블라인드 채용 - 순위 검색

[문제]

프로그래머스

[첫번째 시도]  실패 - 정확성 O/ 효율성 X

# 첫번째 시도: 정확성 테스트 통과 O / 효율성 테스트 통과 X

def solution(info, query):
    answer = []
    info2 = []
    query2  = []
    for i in range(len(info)):
        info2.append(info[i].split())
        info2[i][-1] = int(info2[i][-1])
    for i in range(len(query)):
        query2.append(query[i].split(" and "))
        a = query2[i][-1].find(' ')
        score = int(query2[i][-1][a+1:])
        query2[i][-1] = query2[i][-1][:a]
        query2[i].append(score)
    print("")
    print("info:", info2)
    print("query:", query2)

    for i in range(len(query)):
        count = 0
        for j in range(len(info)):
            if not(query2[i][0] == '-' or info2[j][0] == query2[i][0]):
                continue
            if not(query2[i][1] == '-' or info2[j][1] == query2[i][1]):
                continue
            if not(query2[i][2] == '-' or info2[j][2] == query2[i][2]):
                continue
            if not(query2[i][3] == '-' or info2[j][3] == query2[i][3]):
                continue
            if info2[j][-1] >= query2[i][-1]:
                count += 1
        answer.append(count)
    return answer

def solution2(info, query):
    answer = []
    info2 = []
    query2  = []
    for i in range(len(info)):
        info2.append(info[i].split())
        info2[i][-1] = int(info2[i][-1])
    for i in range(len(query)):
        query2.append(query[i].split(" and "))
        a = query2[i][-1].find(' ')
        score = int(query2[i][-1][a+1:])
        query2[i][-1] = query2[i][-1][:a]
        query2[i].append(score)

    for i in range(len(query)):
        count = 0
        for j in range(len(info)):
            n = 0
            for h in range(4):
                if query2[i][h] == '-' or info2[j][h] == query2[i][h]:
                    n += 1
            if n == 4 and info2[j][4] >= query2[i][4]:
                count += 1
        answer.append(count)
    return answer

[두번째 시도] 성공 - 정확성O/ 효율성O

from itertools import combinations as combi
from collections import defaultdict

def solution(infos, queries):
    answer = []
    info_dict = defaultdict(list)        ## checkpoint1: <defaultdict> info_dict의 default value는 리스트
    for info in infos:
        info = info.split()
        info_key = info[:-1]
        info_val = int(info[-1])
        for i in range(5):
            for c in combi(info_key, i): ## checkpoint2: <combinations> 조합을 튜플 형식으로
                tmp_key = ''.join(c)     ## checkpoint3: <join 함수> 리스트or튜플을 ~으로 연결하여 하나의 문자열로 만듦
                info_dict[tmp_key].append(info_val)
    for key in info_dict.keys():
        info_dict[key].sort()
    
    for query in queries:
        query = query.split(' ')
        query_score = int(query[-1])
        query = query[:-1]

        for i in range(3):
            query.remove('and')          ## checkpoint4: <remove 함수> 리스트의 특정 원소 제거, 단 제일 먼저 나오는 값부터 제거
        while '-' in query:
            query.remove('-')

        tmp_q = ''.join(query)
        if tmp_q in info_dict:
            scores = info_dict[tmp_q] # list
            # query_score보다 같거나 큰 score의 인덱스 구하기
            if len(scores) > 0:
                front, end = 0, len(scores) # (파이썬스러운 문법임!)
                while front < end:       ## checkpoint5: <lower bound 찾기> 이진탐색과 동일한 로직!
                    mid = (front+end) // 2
                    if scores[mid] >= query_score:
                        end = mid
                    else:
                        front = mid+1
                answer.append(len(scores) - front)
        else:
            answer.append(0)
    return answer