이해

• 카카오 회사에 지원한 지원자들 정보를 담은 배열 info와 문의조건이 담긴 배열 query가 매개변수로 주어진다.
• info 배열
  • info 배열의 각 원소의 값은 “개발언어 직군 경력 소울푸드 점수” 형식이다.
  • 개발언어는 cpp, java, python 중 하나
  • 직군은 backend, frontend 중 하나
  • 경력은 junior, senior 중 하나
  • 소울푸드는 chicken, pizza 중 하나
  • 점수는 코딩테스트 점수
• query 배열
  • query 배열의 각 원소의 값은 “[조건] X” 형식이다.
  • [조건]은 “개발언어 and 직군 and 경력 and 소울푸드” 형식이다.
  • 개발언어는 cpp, java, python, - 중 하나
  • 직군은 backend, frontend, - 중 하나
  • 경력은 junior, senior, - 중 하나
  • 소울푸드는 chicken, pizza, - 중 하나
  • ’-‘는 해당 조건을 고려하지 않겠다는 의미이다.
  • X는 코딩테스트 점수를 의미하고, 해당 조건을 만족한는 지원자 중 코딩테스트 점수가 X점 이상인 사람이 모두 몇 명인 지를 의미한다.
• 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return하라.

계획

• 딕셔너리 4개를 선언한다.
  • language 딕셔너리: 언어: {지원자1, 지원자3} 형태로 key: value를 저장한다. 예시) “python”: {1, 3}
  • part 딕셔너리: 직군: {지원자2, 지원자3} 형태로 key: value를 저장한다. 예시) “frontend”: {0, 1}
  • term 딕셔너리: 경력: {지원자1} 형태로 key: value를 저장한다. 예시) “junior”: {1}
  • soulfood 딕셔너리: 소울푸드: {지원자4, 지원자5} 형태로 key: value를 저장한다. 예시) “chicken”: {4, 5}
• 지원자들의 코딩테스트 점수를 나타내는 score 배열을 선언한다.
• 4개의 딕셔너리를 가지고 각 query의 조건을 만족시키는 지원자들의 번호를 원소로 가지는 집합을 구한다.
  • 예시) language[“python”] ∩ part[“frontend”] = {1, 3} ∩ {0, 1} = {1}
• 조건을 만족시키는 지원자 마다 코딩 테스트 점수를 확인하여 X점 이상인 경우에 카운트
• info 길이: N, query 배열 길이: M → 시간 복잡도: O(N*M)

정확성 테스트는 전부 통과했지만 효율성 테스트를 통과하지 못했다.

실행

def solution(info, query):
    language = {"cpp": set(), "java": set(),"python": set(), "-": set(range(len(info)))}
    part = {"backend": set(), "frontend": set(), "-": set(range(len(info)))}
    term = {"junior": set(), "senior": set(), "-": set(range(len(info)))}
    soulfood = {"chicken": set(), "pizza": set(), "-": set(range(len(info)))}
    score = []
    for i, s in enumerate(info):
        l, p, t, so, sc = s.split(" ")

        language[l].add(i)
        part[p].add(i)
        term[t].add(i)
        soulfood[so].add(i)
        score.append(sc)
    
    answer = []
    for q in query:
        
        temp = q.split(" ")
        l, p, t, so, sc = temp[0], temp[2], temp[4], temp[6], temp[7] 

        intersect = language[l] & part[p] & term[t] & soulfood[so]
        answer.append(len([i for i in intersect if int(score[i]) >= int(sc)]))
    return answer  

개선

• 지원자들을 그룹별로 분류한다.
  • 예를 들어, “java backend junior pizza 150” 지원자의 경우 다음 아래의 16개의 그룹에 속하게 된다.
  • “java backend junior pizza”
  • “– backend junior pizza”
  • “java – junior pizza 150”
  • …
  • “– – – -“
• 딕셔너리를 선언하여 그룹: score1, score2, … 형태로 key: value를 저장한다.
• 각 쿼리의 조건을 key값으로 하여 해당 조건을 만족하는 지원자들의 점수들을 담은 배열을 가져와서 이분 탐색을 진행하여 X 이상인 점수의 개수를 센다.
• info 길이: N, query 배열 길이: M → 시간 복잡도: O(M * logN)

def binary_search_opt(arr, x):
    if x > arr[-1]: 
        return len(arr)
    start = 0
    end = len(arr) - 1
    result = int(1e9)
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= x:
            result = min(mid, result)
            end = mid - 1
        else:
            start = mid + 1
    return result

def solution(info, query):
    group = dict()

    for _info in info:
        l, p, t, so, sc = _info.split(" ")
        
        for i in ['-', l]:
            for j in ['-', p]:
                for k in ['-', t]:
                    for w in ['-', so]:
                        key = i+j+k+w
                        if key not in group:
                            group[key] = [int(sc)]
                        else:
                            group[key].append(int(sc))

    for key in group:
        group[key].sort()
    
    answer = []
    for q in query:
        temp = q.replace(" and ", "").split(" ")
        cond = "".join(temp[:-1])
        score = int(temp[-1])
        if cond not in group:
            answer.append(0)
        else:
            answer.append(len(group[cond]) - binary_search_opt(group[cond], score))
    
    return answer

회고

• 문제를 풀면서 효율성 테스트를 통과하지 못할 거라고 생각했는데 역시나 시간초과가 떴다.
• 어려웠지만 계획을 구체적으로 짜서 깔끔하게 잘 푼 것 같았는데 아쉬웠다.
• 이분 탐색 유형을 접한 지 오래돼서 효율성 테스트를 통과할 만한 풀이를 떠올리지 못한 것 같다.
• level2 문제지만 카카오 문제는 역시 까다롭다.