[Python] 순위 검색

1. 문제

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

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

2. 풀이

• dictionary와 이진 탐색을 활용해야 하는 문제
• "-" 를 처리하기 위해 처음에는 - 가 나오면 다른 곳도 탐색하도록 코드를 짰었는데, 그냥 넣을때부터 - 도 넣어주는게 편하다는 것을 나중에 알았다
• dictionary의 키값은 string 도 된다.
  • 뭔가 키 값은 Int여야 할 것 같아서 처음에 3진수로 바꾸어서 풀었는데 정말 부질없는 짓이었음

이진 탐색

이진 탐색이란 :

sort된 배열의 키값을 중앙으로 잡고, 찾는 값이 키값보다 크면 키값 오른쪽을 배열로 잡고 재 탐색, 작으면 왼쪽을 배열로 잡고 재탐색 한다.

• 외워두자..
• 근데 항상 미묘한 = 이나 +1 차이로 틀린다.. 완벽하게 이해를 못한듯.. 특히 중복되는 값이 허용이 되는지 여부에 따라 조금씩 달라지는 듯 하다. ㅠㅠ

 

3. 코드

def solution(info, query):
    answer = []
    
    recruit_dict = {}
    # dict 만들기
    for lang in ["java", "python", "cpp", "-"]:
        for part in ["backend", "frontend", "-"]:
            for career in ["junior", "senior", "-"]:
                for food in ["chicken", "pizza", "-"]:
                    recruit_dict[lang+part+career+food] = []

    # 배열에 잘 넣기
    for i in info:
        lang, part, career, food, score = i.split()
        for _lang in [lang, "-"]:
            for _part in [part, "-"]:
                for _career in [career, "-"]:
                    for _food in [food, "-"]:
                        recruit_dict[_lang+_part+_career+_food].append(int(score))
                        
    for key in recruit_dict.keys():
        recruit_dict[key].sort()

    # print("recruit_dict",recruit_dict)
    # 배열에서 골라서 갯수 세기
    for i in query:
        # print(i)
        lang, a1, part, a2, career, a3, food, score = i.split()
        query_list = recruit_dict[lang+part+career+food]
        # query_list = query_list.sorted(query_list)
        low = 0
        high = len(query_list)
        while low < high:
            mid = (low + high) // 2
            if int(score) <= query_list[mid]:
                high = mid
            else:
                low = mid+1

        answer.append(len(query_list)-low)
    return answer