[프로그래머스] 순위 검색 / 파이썬 / Python / 2021 KAKAO BLIND RECRUITMENT / 카카오 코테 기출

 

💡solutions )

💬 해당 문제는 정확성과 효율성 모두 만족해야 하는 문제다.

 

💬 처음 작성했던 코드는 정확성만 통과했고, 효율성을 만족하지 못했다. for문을 통해 주어진 query정보와  info를 모두 비교하여 만족하는 지원자가 몇 명인지 구하면 정확성은 쉽게 풀 수 있다.

 

💬 문제는 효율성. 혼자서 해결하지 못해서 '카카오 테크 블로그'와 다른 분의 풀이를 참고하며 해결 방법을 생각해봤다.

 

💬 먼저, 해시맵을 활용해 지원자들의 정보를 미리 저장해두는 로직이 필요했다. -> 주어진 info 정보를 key값으로 점수를 value로 하여 딕셔너리에 저장 -> 하나의 info에 총 16가지의 경우의 수가 만들어진다. -> info에서 '-'를 고려하는 경우는 따로 '-'문자를 넣지 않고 주어진 info 조건들만을 모아 key값을 만들었다.

 

e.g) python - junior pizza인 경우 'python-juniorpizza'가 아닌 'pythonjuniorpizza'로 만드는 식

필자의 경우는 추후 query문에서 '-'를 제거했기 때문에 query 조건과 info 정보를 올바르게 비교할 수 있었다.

 

💬 query조건과 info 정보가 일치하는 경우 query_score보다 높은 점수의 지원자가 몇 명인지 구하기 위해 binary search를 사용한다. -> 이를 위해 info_dict의 value값들은 오름차순 정렬한다.

 

💬lower bound 알고리즘을 사용하여 query_score보다 높은 점수의 지원자가 몇 명인지 구한다.

lower bound ?  binary search에서 파생된 알고리즘으로 '원하는 값 이상이 처음 나오는 위치를 찾는 과정'이다.

 

👨‍💻code )

# 정확성, 효율성 모두 통과한 코드👇

from itertools import combinations as combi
from collections import defaultdict


# 점수를 제외한 info 정보를 key값으로, 점수를 value값으로 해시맵 생성
def solution(infos, queries):
    answer = []
    info_dict = defaultdict(list)
    for info in infos:
        info = info.split()
        info_key = info[:-1]
        info_val = int(info[-1])
        for i in range(5):
            for c in combi(info_key, i):  # 하나의 info에서 경우의 수 16개 만들기
                tmp_key = ''.join(c)
                info_dict[tmp_key].append(info_val)  # 가능한 info 조합을 key, 점수를 value로 딕셔너리 저장
    for key in info_dict.keys():
        info_dict[key].sort()  # value값 점수들은 오름차순으로 정리

    for query in queries:
        query = query.split(' ')
        query_score = int(query[-1])
        query = query[:-1]

        for i in range(3):  # and 제거
            query.remove('and')
        while '-' in query:  # '-'제거
            query.remove('-')
        tmp_q = ''.join(query)

        # lower bound 사용해 query_score 보다 큰 점수들의 개수 구하기
        if tmp_q in info_dict:
            scores = info_dict[tmp_q]
            if len(scores) > 0:
                start, end = 0, len(scores)
                while end > start:
                    mid = (start + end) // 2
                    if scores[mid] >= query_score:
                        end = mid
                    else:
                        start = mid + 1
                answer.append(len(scores) - start)
        else:
            answer.append(0)
    return answer

# 정확성만 통과한 코드 👇

def solution(info, query):
    infos = [i.split() for i in info]
    queries = []  # 각 원소 8개씩
    for q in query:
        q = q.split()
        for i in range(3):
            q.remove('and')
        queries.append(q)

    res = [0] * len(query)
    for i in range(len(queries)):
        for info_item in infos:
            for k in range(5):
                if queries[i][k] == '-':
                    continue
                elif k == 4:
                    if int(info_item[k]) >= int(queries[i][k]):
                        res[i] += 1
                elif info_item[k] != queries[i][k]:
                    break

    return res

📌description )

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

---

 

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다. 예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다. 코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가? 물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---