[Programmers]Python_순위 검색

문제

 

문제 설명

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 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점 이상 받은 사람은 모두 몇 명인가?

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

 

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

 

제한사항

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

 

코드

from bisect import bisect_left
from itertools import combinations

def make_all_cases(temp):
    cases = []
    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 += temp[idx]
                else:
                    case += '-'
            cases.append(case)
    return cases

def solution(info, query):
    answer = []
    all_people = {}
    for i in info:
        seperate_info = i.split()
        cases = make_all_cases(i.split())

        for case in cases:
            if case not in all_people.keys():
                all_people[case] = [int(seperate_info[4])]
            else:
                all_people[case].append(int(seperate_info[4]))

    for key in all_people.keys():
        all_people[key].sort()

    for q in query:
        seperate_q = q.split()
        target = seperate_q[0] + seperate_q[2] + seperate_q[4] + seperate_q[6]
        if target in all_people.keys():
            answer.append(len(all_people[target]) - bisect_left(all_people[target], int(seperate_q[7])))
        else:
            answer.append(0)

    return answer

 

풀이

 

예제 #1

 

info = ["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"]

 

query = ["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"]

 

이 문제는 다른 분들의 풀이를 보고 해결했기 때문에 다른 블로그의 글을 봐도 비슷할 것이다.

 

먼저 info 리스트 안에 있는 각 문자열을 split()을 사용하여 분리를 해주어야한다.

"java backend junior pizza 150"를 예를 들어서 설명하자면 ['java', 'backend', 'junior', 'pizza', '150']으로 분리된다. 그리고 점수를 제외한 ['java', 'backend', 'junior', 'pizza']은

 

['javabackendjuniorpizza',

'-backendjuniorpizza',

'java-juniorpizza',

'javabackend-pizza',

'javabackendjunior-',

'--juniorpizza',

'-backend-pizza',

'-backendjunior-',

'java--pizza',

'java-junior-',

'javabackend--',

'---pizza',

'--junior-',

'-backend--',

'java---',

'----']

 

위와 같이 16가지 경우의 query에 속해있을 수 있다.

 

이 같은 모든 경우의 query를 dictionary에 "key : list"형식으로 저장한다. 만약 같은 key라면 당연히 list에 append해야한다.

 

모든 info가 저장되면 각 list를 정렬한다.

 

그럼 이제 query에 있는 값을 key로 검색한다. 그리고 key의 list안에 있는 점수들과 현재 query의 점수를 비교해야한다.

 

이때 bisect 모듈을 사용하여 이분탐색을 실행한다.

 

예를 들어서 list = [50, 80, 150, 210]이고 현재 query의 점수가 100이라면 bisect를 실행했을시 2가 return된다. 왜냐하면 bisect는 100이 list에 없을시 들어가야할 자리(index)를 반환하기 때문이다. 물론 list에 있으면 100의 index값을 반환할 것이다. 따라서 "len(list) - 2 = 2개" 가 되는 것이다.