[프로그래머스][KAKAO_BLIND][2021] 순위 검색

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict
import bisect

lang = ["java", "cpp", "python"]
position = ["backend", "frontend"]
carier = ["junior", "senior"]
food = ["chicken", "pizza"]
categories = [lang, position, carier, food]

def get_key(cat, keyset, i):
    if i == len(categories):
        keyset.append(tuple(cat))
        return

    get_key(cat[:], keyset, i + 1)
    cat[i] = "-"
    get_key(cat[:], keyset, i + 1)

def insert(dic, key, score):
    keyset = []
    get_key(list(key), keyset, 0)
    for k in keyset:
        dic[k].insert(bisect.bisect_left(dic[k],score), score)

def split_key_score(s: str):
    s = s.split(' ')
    key = s[:-1]
    score = int(s[-1])
    while len(key) > len(categories):
        key.remove('and')
    return tuple(key), score

def count_info(dic, q):
    key, limit = split_key_score(q)
    return len(dic[key]) - bisect.bisect_left(dic[key],limit)

def solution(info, query):
    answer = []
    dic = defaultdict(list)

    for i in info:
        key, score = split_key_score(i)
        insert(dic,key,score)

    for q in query:
        answer.append(count_info(dic, q))

    return answer

• get_key
  
  • info의 score insert시 사용
  • 각 key와 "-"의 조합을 재귀로 저장 ( 2 ** 4개 )
• insert
  • info의 score 데이터 저장
  • dict에 각 get_key로 나온 key에 모두 삽입
  • 이 때 biscet로 삽입 위치를 탐색하여 insert
• split_key_score
  • 입력받은 info 또는 query를 key와 score로 분리
• count_info
  • key의 score list에서 limit 이상의 개수를 반환
  • 이 때 정렬되어 있으므로 bisect로 탐색
• 작성한 코드가 계속 시간초과가 나와서 아래 다른 분의 설명을 읽고 작성

 

다른 사람이 작성한 코드

from bisect import bisect_left
from itertools import combinations

def make_all_cases(temp):
    cases = []
    for k in range(5):
        for li in combinations([0, 1, 2, 3], k):
            case = ''
            for idx in range(4):
                if idx not in li:
                    case += temp[idx]
                else:
                    case += '-'
            cases.append(case)
    return cases

def solution(info, query):
    answer = []
    all_people = {}
    for i in info:
        seperate_info = i.split()
        cases = make_all_cases(i.split())
        for case in cases:
            if case not in all_people.keys(): all_people[case] = [int(seperate_info[4])]
            else: all_people[case].append(int(seperate_info[4]))

    for key in all_people.keys():
        all_people[key].sort()

    for q in query:
        seperate_q = q.split()
        target = seperate_q[0] + seperate_q[2] + seperate_q[4] + seperate_q[6]
        if target in all_people.keys():
            answer.append(len(all_people[target]) - bisect_left(all_people[target], int(seperate_q[7]), lo=0, hi=len(all_people[target])))
        else:
            answer.append(0)

    return answer

• 위와 같은 방식으로 작성

https://velog.io/@djagmlrhks3/Algorithm-Programmers-%EC%88%9C%EC%9C%84-%EA%B2%80%EC%83%89-by-Python

[Algorithm] Programmers : 순위 검색 by Python

 

기억해야할 것

• 정말 어려운 문제였다
  
  • 보자마자 트리 형식이 생각났는데, 4개 모두 시간초과
    - "-"인 key가 포함되는 경우 탐색해야하는 리스트들이 급격히 늘어남
  • 트리의 높이 때문인가?하고 모든 key를 만들었는데, 똑같이 4개 모두 시간초과
    - 당연히도... 트리의 높이가 문제가 아니다
  • query가 들어올 때마다 리스트를 sort, bisect로 개수 찾기도 2개 시간초과
    - query마다 sort를 하니까 불필요한 연산이 많아짐
  • 각 값에 삽입시 정렬을 해서야 통과
• bisect로 삽입시 정렬에 사용
  • 정렬해야할 리스트들이 분리되어 있을 때
• 여러 key의 조합을 모두 생성
  • key가 다수이고 key들에 순서를 부여할 경우 영향을 받을 때 ("-"일 경우 문제가 복잡해짐)