프로그래머스 순위 검색(Python)

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

프로그래머스

이번 문제는 정확성 테스트와 효율성 테스트가 있는 문제였습니다. 일단 문제를 읽고 처음에 생각난 대로 바로 코드를 작성했더니 정확성은 통과했지만 효율성에서 모두 실패했었습니다.

저의 시도

간단하게 생각했습니다. 각 query에 대해 지원자 정보를 하나씩 비교해보면서 조건에 맞는 지원자의 수를 세는 방법으로 작성했습니다. 작성한 코드는 아래와 같습니다.

def solution(info: list, query: list):
    answer = []
    for q in query:
        q_list = q.split(" and ")
        q_food, q_score = q_list.pop().split()
        q_list.append(q_food)
        cnt = 0
        for i in info:
            i_list = i.split()
            i_score = i_list.pop()
            for idx in range(len(q_list)):
                if not (q_list[idx] == '-' or q_list[idx] == i_list[idx]):
                    break
            else:
                if int(q_score) <= int(i_score):
                    cnt += 1
        answer.append(cnt)
    return answer

이 코드는 보다시피 3중 for문(...)이 사용됩니다. query 배열의 크기는 최대 100,000이고 info 배열의 최대 크기는 50,000이고 각 지원자마다 5가지 조건을 살펴야 합니다. 그러니 이 코드는 최대 25,000,000,000번의 연산과 비교를 수행하게 됩니다.

다른 사람의 풀이

시간을 단축할 방법을 찾지 못해 결국 다른 사람의 풀이를 보며 배웠습니다.

https://firsteast.tistory.com/103

[프로그래머스] 순위 검색(python)

이 분의 풀이의 핵심은 '그룹화'입니다. 예를 들어 "java backend junior pizza 150" 이라는 지원자 정보는

• "- backend junior pizza 150"
• "java - junior pizza 150"
• "java backend - pizza -"

등과 같은 의미를 가지게 됩니다. 따라서 지원자 정보들을 묶을 수 있는 만큼 묶어서 저장하고 조회하는 방법을 사용했습니다. 아래의 코드가 그 방법을 작성한 코드입니다.

from collections import defaultdict
from itertools import combinations

infos = defaultdict(list)
for i in info:
    i_list = i.split()
    i_score = int(i_list.pop())
        
    for r in range(5):
        possible = list(combinations(range(4), r))
        for p in possible:
            test_cases = i_list[:]
            for t in p:
                test_cases[t] = '-'
            infos['_'.join(test_cases)].append(i_score)
                
for item in infos:
    infos[item].sort()

defalutdict에 대한 설명은 아래 사이트를 보시면 됩니다.

collections — Container datatypes — Python 3.8.13 문서

defaultdict를 통해 key값에 대한 value들을 list에 저장할 수 있게 먼저 선언했습니다. 그리고 점수와 나머지 조건을 따로 분리해서 나머지 조건들을 '-'가 들어갈 수 있는 모든 경우를 구해 이를 key 값으로, 점수를 value값으로 해서 defaultdict에 저장합니다.

마지막에는 defaultdict의 모든 value들을 오름차순으로 정렬합니다.

 

이후에는 각 query마다 query를 key값으로 defaultdict를 조회합니다. 얻은 value는 점수들이 들어간 리스트입니다. 이진 탐색을 통해 점수까지 조건이 맞는 지원자의 수를 셉니다. 여기까지의 설명을 코드로 작성하면 아래와 같습니다.

from collections import defaultdict
from itertools import combinations

def solution(info: list, query: list):
    answer = []
    infos = defaultdict(list)
    for i in info:
        i_list = i.split()
        i_score = int(i_list.pop())
        
        for r in range(5):
            possible = list(combinations(range(4), r))
            for p in possible:
                test_cases = i_list[:]
                for t in p:
                    test_cases[t] = '-'
                infos['_'.join(test_cases)].append(i_score)
                
    for item in infos:
        infos[item].sort()

    for q in query:
        q = q.replace('and', '').split()
        organised_q = '_'.join(q[:-1])
        q_score = int(q.pop())

        if organised_q in list(infos):
            data = infos[organised_q]
            
            if len(data) > 0:
                lower, upper = 0, len(data)
                while lower != upper and lower != len(data):
                    if data[(lower + upper) // 2] >= q_score:
                        upper = (lower + upper) // 2
                    else:
                        lower = (lower + upper) // 2 + 1
                answer.append(len(data) - lower)
        else:
            answer.append(0)
    return answer

프로그래머스에서 채점한 결과 효율성 테스트에서 최대 1179.09ms, 39.4MB 소모했습니다.