[프로그래머스-파이썬] 순위검색

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

 

def solution(info, query):
    answer = []
    q = len(query)
    people = []
    terms = []
    for i in info:
        person = list(i.split())
        people.append(person)
    
    for j in query:
        term = list(j.split())
        term = [t for t in term if t != 'and']
        terms.append(term)

    for t in terms:
        candidate = [p for p in people if int(p[-1])>= int(t[-1])]
        
        
        for k in range(4):
            if t[k] == '-':
                continue
            candidate = [c for c in candidate if c[k]==t[k]]

        answer.append(len(candidate))

    return answer

 

이렇게 풀면 문제는 풀리지만 효율성에서 탈락이다. 왜냐면 candidate를 비교하는데 너무 많은 자원이 들기 때문이다. 해당 코드는 O(len(query)*N)의 시간복잡도를 가지기 때문에 query가 많아질수록 결과적으로 O(N^2)의 시간복잡도를 가져서 효율성에서 0점 나온다..

 

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    answer = [] 
    data = {}
    
    for applicant in info:
        applicant = (applicant.split())
        score = int(applicant[-1])
        applicant = applicant[:-1]
        
        for i in range(5):
            for c in combinations(range(4), i):
                key_list = list(applicant)
                for k in c:
                    key_list[k] = '-'
                
                key = tuple(key_list)
                
                if key not in data:
                    data[key] = [score]
                else:
                    data[key].append(score)

    for key in data:
        data[key].sort()
    
    for q in query:
        q = q.replace("and ", "").split()
        q_score = int(q[-1])
        q = tuple(q[:-1])
        
        if q in data:
            scores = data[q]
            
            target = bisect_left(scores, q_score)
            answer.append(len(scores)-target)
        else:
            answer.append(0)
    
    return answer

 

효율성검사를 위한 새코드이다. 질문하기가 70개가 넘길래 만만하지 않다고 생각은 했는데 아이디어를 보고서도 쉽진 않았다.

난 딱 이 문제에 당면했고, 이 3번 설명이 와따였음.

이 코드의 방식은 1. info로 여러 키가 될 수 있는 조합을 미리 만들 것 2. 그 조합이 실제 query에 있는지 확인할 것.

코드상 특이점은 bisect_left로 개수를 체크했단거? 이 함수는 O(logN)의 시간복잡도를 가지고 있다고 한다. 그냥 for문을 쓰면 또 O(n)만큼 쓰기 때문에 효율성 검사에서 탈락이다. 

아 문제를 푸는 것보다 잘푸는 건 훨씬 어렵다.