[Programmers] 순위 검색

🎯 programmers > 2021 KAKAO BLIND RECRUITMENT > 순위 검색

---

🤔 나의 풀이

📌 문제

- programmers > 2021 KAKAO BLIND RECRUITMENT > 순위 검색

📌 날짜

2021.06.25

📌 시도 횟수

Failed

❌ 첫번째 시도 (정확성 100/효율성 0)

• 첫번째 풀이에서는 평소 우리가 구하는 방법 그대로 코드로 구현했다.

• 지원자 정보에서 조건을 차례대로 검사해나가면서, 조건을 만족하지 않는 경우는 다음 검색 대상에서 지워나가는 방식이다.
  

• 오답의 원인

- info 배열의 크기는 1~50000이다.
- query 배열의 크기는 1~100000이다.
- 이 방법은 매번 query의 각 조건을 검사할 때마다 info를 무조건 모두 검사해야 된다.
- 게다가 마지막 점수를 찾을 때에도 최악의 경우, 한번 더 모든 info를 검사해야된다.
- 그야말로 최악의 호율성!

---

❌ 두번째 시도 (정확성 100/효율성 0)

• 첫번째 시도에서 점수를 찾는 과정을 이진 탐색을 사용했다.
• 여전히 효율성에서 시간 초과가 발생한다.
• 단순히 점수를 판별하는 과정을 이진 탐색으로 바꾸었다고 효율성이 통과되지는 않는다.

---

👊🏻 세번째 시도 (정확성 100/효율성 100)

• 결국 카카오 코딩테스트 해설을 참고했다. 물론 그래도 잘 이해가 안돼서 다른 분들의 코드도 참고해서 겨우 풀었다. (이게 Lv2라니..)

⭐문제 해결 과정

1. 각 info(지원자)에 대해 해당 조건을 만족할 수 있는 모든 경우를 구한다.

• 가능한 모든 경우는 available_cases이라는 dict로 저장한다.
• available_cases의 key 값은 info(지원자 정보) 중 [언어, 직군, 경력, 소울 푸드] 정보이다.
• available_cases의 value 값은 해당 조건([언어, 직군, 경력, 소울 푸드])을 만족하는 info(지원자)들의 점수 리스트이다.
• 예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 된다.
  
• 그리고 이렇게 구한 16가지 경우를, key값으로 사용하여 value에 현재 지원자의점수를 추가한다.
• 이것을 모든 info에 대해 반복하여 구한다.

def add_available_cases(info):
    available_cases = defaultdict(list)
    for i in info:
        info_list = i.split()
        for a in (info_list[0], "-"):
            for b in (info_list[1], "-"):
                for c in (info_list[2], "-"):
                    for d in (info_list[3], "-"):
                        key = str(a + b + c + d)
                        available_cases[key].append(int(info_list[-1]))
    return available_cases

---

2. 이제 모든 준비가 끝났다! 지금부터는 query(조건)을 하나씩 돌면서, available_cases에서 key가 query(조건)일 때의 value를 가져온다.

• available_cases에서 key가 query(조건)일 때의 value는, query의 조건을 만족하는 모든 info(지원자)의 점수 정보 리스트이다.
• 이때 이 점수 리스트를 candidate_list(후보자 리스트)라고 하자. '후보자'인 이유는 아직 마지막 조건인 점수 조건은 검사하지 않았기 때문이다.
• 점수 조건을 효율적으로 검사하기 위해서는 두번째 시도에서 언급한 이진 탐색의 lower bound(처음으로 k보다 같거나 큰 값)를 구하는 방법을 통해 구하면 효율성 측면에서 효과적으로 구할 수 있다.
• 단, 이진 탐색을 구현하려면 먼저 숫자 리스트를 정렬 해주어야 한다.

# 숫자 리스트 정렬
def sort_available_cases(available_cases):
    for key, value in available_cases.items():
        available_cases[key] = sorted(value)
    return available_cases
  
# 이진 탐색으로 lower_bound 구해서 만족하는 경우 찾기
def lower_bound(candidate_list, key):
    result = 0
    start, end = 0, len(candidate_list)
    while start < end:
        mid = (start + end) // 2
        if candidate_list[mid] >= key:
            end = mid
        else:
            start = mid + 1

    # 최종적으로 리턴하는 값은 lower_bound보다 큰 값의 개수이다.
    return len(candidate_list) - end

• 따라서 최종적으로 len(candidate_list) - end를 리턴한다. 즉, 후보자들 중 하한(OOO점 이상)보다 크거나 같은 info(지원자)들이 몇 명인지 구해서 리턴한 것이다.

---

👏🏻 최종 코드

• 따라서 최종 코드는 다음과 같다 :D

import re
from itertools import combinations
from collections import defaultdict


def add_available_cases(info):
    available_cases = defaultdict(list)
    for i in info:
        info_list = i.split()
        for a in (info_list[0], "-"):
            for b in (info_list[1], "-"):
                for c in (info_list[2], "-"):
                    for d in (info_list[3], "-"):
                        key = str(a + b + c + d)
                        available_cases[key].append(int(info_list[-1]))
    return available_cases


def sort_available_cases(available_cases):
    for key, value in available_cases.items():
        available_cases[key] = sorted(value)
    return available_cases


def parse_query(query):
    query_list = list(re.sub("and ", "", query).split())
    return "".join(query_list[:-1]), int(query_list[-1])


def lower_bound(candidate_list, key):
    result = 0
    start, end = 0, len(candidate_list)
    while start < end:
        mid = (start + end) // 2
        if candidate_list[mid] >= key:
            end = mid
        else:
            start = mid + 1

    return len(candidate_list) - end


def solution(info, queries):
    available_cases = add_available_cases(info)
    sorted_cases = sort_available_cases(available_cases)

    answer = []
    for query in queries:
        query_list, query_num = parse_query(query)
        candidate_list = available_cases[query_list]
        answer.append(lower_bound(candidate_list, query_num))
    return answer

---

🥺 느낀점

- 이게 Lv2라니..............ㅠ😭😭
- 정확성은 그럭저럭 풀겠는데... 
효율성은 문제 해설 안 봤으면 못 풀었을 것 같다.. ㅠㅠ