[Programmers 72412] 순위검색

문제

LV2 [Programmers 72412 - 순위검색]

문제 풀이 방법

이전에 풀어본 적 있는 문제이지만, 다른 사람의 풀이를 참고하고 풀었었기 때문에 다시 풀어보았다. 검색해야 할 데이터 값이 1000만이 넘어가는 경우는 이진탐색 알고리즘을 사용하여 검색하는 것이 좋다는 개념을 이번에 다시 한번 확실하게 배울 수 있었다. 처음부터 단순 탐색을 하면 효율성 테스트를 통과하지 못한다.

1. database라는 dictionary를 만들어서 나올 수 있는 모든 경우를 초기화해준다.
2. info배열을 읽으면서 dictionary에 score를 추가해준다.
3. dictionary를 score를 기준으로 배열해준다.

4. query를 읽으면서 dictionary에서 검색할 key를 추출하여 score 배열에서 점수를 검색한다.

   이 때, score는 배열되어 있으므로 이진탐색을 이용하여 검색한다!!

풀이 코드

Python

import bisect

def solution(info, query):
    answers = []
    database = {}
    for language in ['cpp', 'java', 'python', '-']:
        for job in ['backend', 'frontend', '-']:
            for career in ['junior', 'senior', '-']:
                for food in ['chicken', 'pizza', '-']:
                    database[language+job+career+food] = []
    for i in info:
        language, job, career, food, score = i.split()
        for l in [language, '-']:
            for j in [job, '-']:
                for c in [career, '-']:
                    for f in [food, '-']:
                        database[l+j+c+f].append(int(score))

    for key in database.keys():
        database[key].sort()
        
    for q in query:
        arr, score = q.replace(" and ","").split()
        idx = bisect.bisect_left(database[arr], int(score))
        answer = len(database[arr]) - idx
        answers.append(answer)
    return answers

print(solution(["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"],
               ["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"]))