[프로그래머스] lv2. 순위 검색

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

프로그래머스

 

내 풀이

import re

def remove_etc(str_list):
    removed_list = [re.sub(r'and ', '', x) for x in str_list]
    return removed_list
    
def solution(info, query):
    answer = []
    info = (remove_etc(info))
    info = [x.split() for x in info]
    query = remove_etc(query)
    query = [x.split() for x in query]
    for i in range(len(query)):
        ans = 0
        qwords = query[i]
        for j in range(len(info)):
            flag = 1
            for k in range(len(qwords)-1):
                if qwords[k] != '-' and qwords[k] != info[j][k]:
                    flag = 0
                    break
            if flag == 1 and int(info[j][-1]) >= int(qwords[-1]):
                ans += 1
        answer.append(ans)
        
    return answer

풀면서 효율성 테스트 통과 못할 거 같았는데 예상했던대로 효율성 테스트는 실패다.

    

다른 사람의 풀이

import bisect, itertools, collections

def solution(info, query):
	# value가 기본으로 list인 dictionary 생성
    info_dict = collections.defaultdict(list)
    # cartesian product (repeat=4 : 1111, 1110, 1101, ... 0000)
    binary = list(itertools.product([1, 0], repeat=4))
    for inf in info:
        inf_split = inf.split()
        for bi in binary:
            key = ''.join([inf_split[i] if bi[i]==1 else '-' for i in range(4)])
            info_dict[key].append(int(inf_split[4]))
            
    # 이분 탐색을 위한 정렬
    for k in info_dict.keys():
        info_dict[k].sort()
        
    answers = []
    for q in query:
        [a, _, b, _, c, _, d, score] = q.split()
        kk = a + b + c + d
        # 이분탐색
        idx = bisect.bisect_left(info_dict[kk], int(score))
        answers.append(len(info_dict[kk]) - idx)
    return answers

 

- collections.defaultdict(default_factory) : value가 default_factory 형인 dictionary 

- itertools.product : 데카르트곱(cartesian product) 

예: itertools.product('ABCD', repeat=2) : AA, AB, AC, AD, BA, BB, ... , DC, DD (n*n개, 16개)

itertools.product([1, 0], repeat=4) : 1111, 1110, 1101, 1011, 01111, 01111, ..., 0001, 0000 (n*n*n*n개, 16개)

 

- bisect.bisct_left(리스트, 찾을 값)

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

 

 

 

참고

https://docs.python.org/3/library/collections.html

collections — Container datatypes

https://docs.python.org/ko/3/library/itertools.html

itertools — Functions creating iterators for efficient looping

https://docs.python.org/ko/3.7/library/bisect.html