[Python] Programmers 순위 검색

1. 문제 링크

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

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

---

2. 문제 요약

• query 조건에 맞는 지원자 찾기
• 총 4가지 항목 + 점수 조건

⇒ 쉬워 보이지만... 문제에 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 적혀있다.

---

3. 아이디어 정리

아이디어 1. 쿼리를 하나씩 돌리면서 조건에 맞는 사람 count

• 정확성을 맞지만, 효율성에서는 통과 못한다.

아이디어 2.카카오 문제 해설 참고 아이디어

2021 카카오 신입 공채 1차 온라인 코딩 테스트 for Tech developers 문제 해설

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

1. 지원자가 가질 수 있는 case를 dict 리스트에 점수를 넣어준다. ⇒ 한 지원자 당 16가지의 조합이 나온다.
   • ex) java backend junior pizza 150 인 지원자의 경우 아래 표와 같이 생성이 된다.

     

      한 지원자 당 16가지 조합 생성 

   • dict 리스트에 아래와 같이 저장해준다. key는 지원자 정보 조합, value는 해당 지원자 점수 넣기

     

     조합을 dict 로 저장 

2. dict에 있는 리스트 점수를 이분 탐색해서 구하기 위해 sorting를 해준다.
3. 쿼리 하나씩 돌리며 해당 조건에 있는 dict 찾아 점수는 이분 탐색으로 몇 명이 조건에 맞는지 결과를 저장한다.

---

4. 문제 풀이

4-1. 내 풀이

"""
참고: https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1
"""

from bisect import bisect_left
from itertools import combinations
from collections import defaultdict

def get_combinations(people):
    """
    한 사람당 16가지 조합 만들기 - 4가지 항목에 대한 o, - 케이스 생성 
    """
    cases = []
    # 0,1,2,3 개 선택하면서 - 해당 조합에 -넣기
    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 += people[idx]
                else:
                    case += '-'
            cases.append(case)
    return cases

def solution(info, query):
    answer = list()
    all_info = defaultdict(list)
    # 1. info에 대한 정보에서 모든 케이스를 만들어준다 => 총 16가지 종류
    for i in info:
        i = i.split()
        case = get_combinations(i)
        for c in case:
            all_info[c].append(int(i[-1]))

    # 2. dict에 있는 리스트 점수를 이분 탐색해서 구하기 위해 sorting
    for k in all_info.keys():
        all_info[k].sort()

    # 3. 쿼리 하나씩 돌려 해당 조건에 있는 dict를 찾아 이분탐색으로 점수에 맞는 사람 찾기 
    for q in query:
        q = q.replace("and","").split()
        score = int(q.pop())
        q = "".join(q)
        print(bisect_left(all_info[q], score))
        # bisect_left: score 위치 반환. 전체 길이 - 위치 = score이상의 사람 수
        answer.append(len(all_info[q]) - bisect_left(all_info[q], score))
    return answer

---

5. 결론

• dict로 모든 결과를 넣어서 이분탐색으로 찾는 문제이다.
• 너무 어려운 문제...😿