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

1.문제

programmers.co.kr/learn/courses/30/lessons/72412

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

2.풀이

효율성을 통과하느라 다시 풀었던 문제.

처음에 2중 for문으로 풀었을 때 정확도는 통과했지만 효율성에서 시간 초과가 났다..

풀이를 찾아보니 미리 지원자 정보의 조합을 저장해놓고 score를 비교하는 방식으로 풀어야했다!

 

python의 combinations 라이브러리로 각 지원자의 조합을 구해서 딕셔너리의 key 로 사용하고 그 때의 score를 value로 저장했다.

마지막에 query의 score과 비교해서 점수 이상이면 그 수 (index의 차이로 구함)를 answer에 추가한다.

이 때 점수비교하는 것은 미리 sorting 을 해주고 바이너리 서치로 탐색 시간을 줄여주었다.

 

1) dict로 지원자의 조합 key - 점수 value 로 저장

2) score 를 오름차순 sorting

3) 바이너리 서치로 query의 점수와 비교하여 정답 개수 구함

 

3.코드

# 개발언어, 직군, 경력, 소울푸드
# 조건을 만족하는 사람중 X점 이상인 사람 수
from itertools import combinations 

def solution(info, query):
    answer = []
    info_dict = {}
    
    for x in info:
        li = x.split()
        info_key = li[:-1]
        info_val = int(li[-1]) #score
        for i in range(5):
            for c in combinations(info_key, i):
                tmp_key = ''.join(c)
                if tmp_key in info_dict:
                    info_dict[tmp_key].append(info_val)
                else:
                    info_dict[tmp_key] = [info_val]
                
    for key in info_dict.keys():
        info_dict[key].sort()  #value(score)을 오름차순으로 정렬
        
    # for k, v in info_dict.items():
    #     print(k ,v)
    for qu in query:
        q = qu.split(' ')
        q_score = int(q[-1])
        q_query = q[:-1]
        
        while 'and' in q_query:
            q_query.remove('and')
        while '-' in q_query:
            q_query.remove('-')
        q_query = ''.join(q_query)
        #print(q_query)
        if q_query in info_dict:
            scores = info_dict[q_query]
            if len(scores)>0:
                start, end = 0, len(scores)
                while start < end:
                    mid = (start + end) // 2
                    if scores[mid] >= q_score:
                        end = mid
                    else:
                        start = mid + 1
                answer.append(len(scores) - start)
        else:
            answer.append(0)
        
    return answer