# 순위검색 - 2021 KAKAO BLIND

https://programmers.co.kr/learn/courses/30/lessons/72412?language=python3

• 문제
  DB에 저장되어 있는 정보에 대하여, 각 쿼리에 대해 일치하는 사람의 수를 구하기.

• 제한사항
  - info 배열의 크기는 1 이상 50,000 이하
  - query 배열의 크기는 1 이상 100,000 이하

• 파이썬 코드1.
  - 무식한 완전탐색 : 효율성 테스트 실패

def insertQuery(query):
    query_all = []
    for que in query :
        query_lst= que.split(' and ')
        temp = query_lst.pop()
        query_lst.extend(temp.split())
        score = int(query_lst.pop())
        query_lst.append(score)
        query_all.append(query_lst)
    return query_all


def insertData(info) :
    data_base = []
    for i in info :
        person = i.split()
        score = int(person.pop())
        person.append(score)
        data_base.append(person)
    return data_base


def solution(info, query):
    answer = []
    data_base = insertData(info)
    query_lst = insertQuery(query)

    for que in query_lst:
        number = 0
        for data in data_base:
            if que[0] == '-' or que[0] == data[0] :
                if que[1] == '-' or que[1] == data[1] :
                    if que[2] == '-' or que[2] == data[2] :
                        if que[3] == '-' or que[3] == data[3] :
                            if data[-1] >= que[-1] :
                                number += 1
        answer.append(number)

    return answer

• info 배열(길이 n)과, query 배열(길이 m)의 크기만큼 이중 for문이 돌아가고, 리스트의 각 요소를 모두 비교하는 탐색이므로, 시간복잡도 O(n*m) 으로 실패.
• 그 외에도 문자열 처리시, 점수를 int로 변환하는 부분 간과하여 시간 낭비함.
• DB에 미리 처리될 수 있는 정보를 미리 가공해두고, 쿼리 검색시는 이미 가공된 정보를 이용해 최소한의 operation만 하도록 설계해야 효율성 테스트 통과가 가능할 듯 하다.

• 파이썬 코드2.

  • make_dict 함수 생성 : 주어진 info를 파라미터로, 가능한 모든 경우의 수(각 정보당 16개)에 대한 key에 대하여, 오름차순 정렬된 score 리스트를 가지는 defaultdict 객체를 반환한다. 즉 info의 모든 정보가 담긴 dict객체를 반환.
  • 각 쿼리의 정보로 key를 생성하고, 위에서 만든 dict에서 해당 정보 검색 후, 주어진 점수 이상의 값을 갖는 value의 개수를 찾아(lowerbound 이진탐색 이용:bisect_left), answer에 추가한다.

from collections import defaultdict
from bisect import bisect_left

def make_dict(info):
    data_dict = defaultdict(list)
    for cur in info:
        person = cur.split()
        score = int(person.pop())
        # make keys for dict
        keys = [''.join(person), '----']
        for i in range(4):
            base = ['-', '-', '-', '-']
            base[i] = person[i]
            keys.append(''.join(base[:]))
            temp = base[:]
            temp[(i + 2) % 4] = person[(i + 2) % 4]
            keys.append(''.join(temp[:]))
            base[(i + 1) % 4] = person[(i + 1) % 4]
            keys.append(''.join(base[:]))
            base[(i + 2) % 4] = person[(i + 2) % 4]
            keys.append(''.join(base[:]))
        keys = set(keys)
        # input score into all the keys above
        for key in keys:
            data_dict[key].append(score)
    # sort the values of each key
    for key in data_dict:
        data_dict[key].sort()        
    return data_dict


def solution(info, query):
    answer = []
    data_dict = make_dict(info)

    for que in query:
        query_lst = que.split(' and ')
        temp = query_lst.pop()
        query_lst.extend(temp.split())
        score = int(query_lst.pop())
        que_key = ''.join(query_lst)
        score_lst = data_dict[que_key]
        cnt = len(score_lst) - bisect_left(score_lst, score)
        answer.append(cnt)
    return answer

• 효율성 테스트
  테스트 1 〉 통과 (620.70ms, 42.4MB)
  테스트 2 〉 통과 (628.98ms, 43MB)
  테스트 3 〉 통과 (625.48ms, 42.3MB)
  테스트 4 〉 통과 (630.20ms, 42.6MB)

모든 테케에 대해서 유사한 수준의 시간, 메모리를 사용한다.

• 모든 경우의 수(각 정보 당 16가지)에 대해 모두 처리를 해야겠다는 접근을 하기가 쉽지 않음
• 아래 구현에 대해 고민이 필요했기에 접근 방법을 카카오테크 블로그로 참고하고 나서도 시간이 꽤 걸렸다.
  1. 각 info 원소당 16가지 경우의 수에 대해 키 생성하기.
  2. 전체 dict에 키 오류 없이 저장 -> defaultdict(list) 객체 이용
  3. 저장된 score를 쿼리의 score와 비교하기.

• 참고문헌
  - kakao tech blog 풀이 : https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
  - bisect 라이브러리 doc : https://docs.python.org/3/library/bisect.html