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

링크

순위검색

풀이

• "주어진 문자열을 어떤 방식으로 split할 것인가?"

완전탐색을 이용해 풀려고 했으니 특정 문자열을 내가 원하는 형식으로 만드는 것이 가장 중요하다.

먼저 주어진 query가 info 형식으로 변환될려면 " and" -> ""로 변경한 후 split(" ")을 하면 된다.

 

• "후보 쿼리는 어떤 방식으로 생성한 것인가?"

먼저 후보 쿼리를 직접 만들면 몇 개의 후보가 나올 수 있을지 생각을 해보자.
경우의 수는 두 가지 임으로 2 x 2 x 2 x 2 = 16개의 후보가 생성된다.

그럼 어떤 방식으로 생성할 것인가 조합함수를 이용해서 해당하는 인덱스를 '-' 문자열로 변경하면 모든 후보군을 생성할 수 있다.

 

• "정렬된 리스트에서 특정 값을 빠르게 찾는 방법"

이분 탐색을 수행하면 된다. 파이썬에서는 bisect이라는 모듈이 해당 기능을 지원한다.

 

코드

import bisect
from copy import deepcopy
from itertools import combinations


def make_sub_query(info):
    keys = []
    keys.append(" ".join(info))
    for k in range(1, 5):
        for sub in list(combinations(range(0, 4), k)):
            case = deepcopy(info)

            for idx in sub:
                case[idx] = '-'

            keys.append(" ".join(case))
    return keys


def solution(infos, querys):

    info_dict = {}
    
    for info in infos:
        lang, ground, pos, food, score = info.split()
        query_set = make_sub_query([lang, ground, pos, food])

        for q in query_set:
            if q in info_dict.keys():
                info_dict[q].append(int(score))
            else:
                info_dict[q] = [int(score)]

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

    answer = []

    for q in querys:
        q = q.replace(" and", "")
        lang, ground, pos, food, score = q.split()

        query_of_key = " ".join([lang, ground, pos, food])

        if query_of_key in info_dict.keys():
            score_list = info_dict[query_of_key]
            answer.append(len(score_list) - bisect.bisect_left(score_list, int(score)))

        else:
            answer.append(0)

    return answer
    

if __name__ == "__main__":
    info = ["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"]
    query = ["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]
    print(solution(info, query))

 

후기

이 당시 코딩테스트에서도 해당 문제를 못 푼 기억이 있었다. 이번에 사용했던 접근 방식은 완전탐색을 이용해 후보 쿼리를 만든 후 만들어진 쿼리를 이용하는 것이었다. 하지만 실패했다. 실패한 이유는 크게 3가지가 있다. 

 

1, 시간 초과 -> 단위 마다 구현한 후 테스트하는 방식이 필요함(TDD를 통해서 해결)

2. 특정 문자열을 깔끔하게 split하는 방식이 생각이 안남 -> 문자열 다루기 문제로 연습

3. 완전탐색을 이용해 후부 문자열을 전부 만들고 탐색할 생각을 함 -> 계산 시간을 고려하지 않았음

 

앞으로 더 열심히 노력해야겠다