[2021 카카오 블라인드] 순위 검색 파이썬 풀이

프로그래머스 문제 링크

정확도는 금방 통과했는데, 효율성 테스트가 헬이었다.

정확도만 맞춘 무식한 방법은 다음과 같다.

def solution_brute_force(info, query):
    answer = []
    # 1. 전처리 
    processed_query = []
    processed_info = []
    for q in query:
      split = q.split()
      processed_query.append(
        [v for idx,v in enumerate(split) if (idx%2 == 0 or idx==len(split)-1)]
      )
    for q in info:
      split = q.split()
      processed_info.append(split)

    for query in processed_query:
      count = 0
      for info in processed_info:
        if int(query[4]) > int(info[4]):
          continue
        matches = True
        for i in range(0,4):
          if query[i]!='-' and query[i]!=info[i]:
            matches = False
      
        if matches:
          count+=1
      answer.append(count)
        
    return answer

그냥 무작정 세는 것.~~

근데 이렇게 쉬울 리는 없고 당연히 효울성을 따져야한다.

해쉬로 풀어야될것같은 느낌은 왔는데 해쉬로 계속 해도 통과가 안되는 것은 해쉬 + 이진탐색 까지 써야했기 때문이다.

from collections import defaultdict
import bisect
# hash
def solution(info, query):
  answer = []
  info_dict = defaultdict(list)

  for i in info:
    _info = i.split()
    # 이거는 product를 써서 더 깔끔하게 할 수도 있당
    allowed_queries = [
      _info[0]+_info[1]+_info[2]+_info[3],
      '-'+_info[1]+_info[2]+_info[3],
      _info[0]+'-'+_info[2]+_info[3],
      _info[0]+_info[1]+'-'+_info[3],
      _info[0]+_info[1]+_info[2]+'-',
      '-'+'-'+_info[2]+_info[3],
      '-'+_info[1]+'-'+_info[3],
      '-'+_info[1]+_info[2]+'-',
      _info[0]+'-'+'-'+_info[3],
      _info[0]+'-'+_info[2]+'-',
      _info[0]+_info[1]+'-'+'-',
      _info[0]+'-'+'-'+'-',
      '-'+'-'+'-'+_info[3],
      '-'+_info[1]+'-'+'-',
      '-'+'-'+_info[2]+'-',
      '-'+'-'+'-'+'-'
    ]
    for q in allowed_queries:
      bisect.insort(info_dict[q], int(_info[4]))
  for q in query:
    _query = q.split()
    key = _query[0]+_query[2]+_query[4]+_query[6]
    count = len(info_dict[key])-bisect.bisect_left(info_dict[key], int(_query[-1]))
    answer.append(count)

  return answer

여기서 중요한건 bisect를 쓰는거...
그냥 이진탐색 직접 구현해서 했는데도 통과가 안돼서 질문하기 쪽 글들 보니까 python에서 bisect를 써야 통과가 된다는 소문이 있었다 ㅠㅠ

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

이런게 있구나.. 처음 깨닫고 앞으로 유용하게 쓸 예정!

(추가: product로 깔끔하게 바꾸기)

from collections import defaultdict
from itertools import product
import bisect
# hash
def solution(info, query):
  answer = []
  info_dict = defaultdict(list)

  for i in info:
    _info = i.split()
    allowed_queries = list(product(*[
      [_info[0], '-'],
      [_info[1], '-'],
      [_info[2], '-'],
      [_info[3], '-']
    ]))
    for q in allowed_queries:
      bisect.insort(info_dict[''.join(list(q))], int(_info[4]))
  for q in query:
    _query = q.split()
    key = _query[0]+_query[2]+_query[4]+_query[6]
    count = len(info_dict[key])-bisect.bisect_left(info_dict[key], int(_query[-1]))
    answer.append(count)

  return answer