문제 설명

구현 아이디어

00이며 00이며 00 ... → set 자료형을 사용해서 교집합으로 표현하자.

• key: 언어, 직군, 경력, 소울 푸드, 점수 / value: 지원자 인덱스
  ex) 'java': {0, 4}, 'backend': {0, 3, 4, 5} 일 때,
  java로 코딩테스트를 봤으며, backend 직군을 선택한 사람은 java & backend

전체 코드 - 틀렸습니다.

from collections import defaultdict

def solution(info, query):
    answer = []
    status = [defaultdict(set) for _ in range(5)]
    
    for i in range(len(info)):
    	# 문자열 형태로 들어온 입력을 분리한다.
        # "java backend junior pizza 150"
        arr = list(info[i].split())
        
        # 언어, 직군, 경력, 소울 푸드, 점수별로 딕셔너리에 값 대입
        for j in range(5):
            if j == 4: # 점수인 경우, key를 int형으로 저장
                status[j][int(arr[j])].add(i)
            else:
                status[j][arr[j]].add(i)
        
    for q in query:
    	# 문자열 형태로 들어온 입력을 분리한다.
        # "java and backend and junior and pizza 100"
        condition = q.split()
        result = set(i for i in range(len(info))) # 조건을 만족하는 지원자의 인덱스
        
        # arr 리스트에 요구하는 조건 저장
        arr = []
        for elem in condition:
            if elem == 'and':
                continue
            arr.append(elem)
        # 결과: ['java', 'backend', 'junior', 'pizza', '100']
        
        for i in range(len(arr)):
            if arr[i] == '-':
                continue
            if i == 4: # 점수의 경우, 00점 '이상'이기 때문에 교집합을 따로 계산
                temp = set()
                for key in status[i].keys():
                    if key >= int(arr[i]):
                        temp = temp | status[i][key]
                result = result & temp
            else:
                result = result & status[i][arr[i]]
        
        
        answer.append(len(result))
    
    return answer

정확성 테스트는 통과하였으나, 효율성 테스트에서 시간 초과가 나온다 😔

구현 아이디어 2

문제를 다시 읽어보자

종류가 한정적인 개발언어, 직군, 경력, 소울푸드와 다르게 점수의 범위는 매우 크다.
그렇기 때문에 점수를 딕셔너리 형태로 관리하는 것은 적합하지 않은 방법이다.

그래서

개발언어, 직군, 경력, 소울푸드까지 교집합으로 구한 뒤,
해당 교집합에서 이분 탐색을 진행하여 조건을 만족하는 지원자가 몇 명인지 구하자.

전체 코드

from collections import defaultdict
from bisect import bisect_right

def solution(info, query):
    answer = []
    status = [defaultdict(set) for _ in range(4)]
    scores = [] # 점수를 저장할 리스트
    for i in range(len(info)):
        arr = list(info[i].split())
        
        for j in range(5):
        	# 점수는 따로 저장
            if j == 4:
                scores.append(int(arr[j]))
                continue
            status[j][arr[j]].add(i)
           
    for q in query:
        result = set(i for i in range(len(info)))
        condition = []
        score = 0
        for elem in q.split():
            if elem == 'and':
                continue
            # 점수는 따로 저장
            if elem.isdigit():
                score = int(elem)
                continue
            condition.append(elem)
        
        
        for i in range(len(condition)):
            if condition[i] == '-':
                continue
            result = result & status[i][condition[i]]
        
        # 개발언어, 직군, 경력, 소울푸드 조건을 만족하는 사람들의 점수가 담긴 리스트
        temp = sorted([scores[i] for i in range(len(scores)) if i in result])
        # 조건 점수 이상인 사람들의 수를 a에 저장
        a = len(temp) - bisect_right(temp, score) + temp.count(score)
        answer.append(a)
    
    return answer

정확성 테스트에서 실행 시간은 개선되었으나, 효율성 테스트는 여전히 통과하지 못한다

구현 아이디어 3

결국 2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설을 참고하여 문제를 풀 수 있었다.

예를 들어, java backend junior pizza 150 지원자의 경우 다음과 같이 16가지 그룹에 속하게 된다.
이 지원자는 - backend junior pizza 150이나 - - junior pizza 150에도 속한다.

그러므로

key를 16개의 경우의 수, value를 score로 하여 딕셔너리를 만든다.
조건을 만족하는 지원자를 찾을 때, 조건을 key로 하여 점수 리스트를 얻는다.
점수 리스트를 정렬한 뒤 이분 탐색을 진행하여 지원자 수를 빠르게 찾는다.

전체 코드

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

def solution(infos, queries):
    answer = []
    
    d = defaultdict(list)
    
    for info in infos:
        info = info.split()
        condition = info[:-1]
        score = int(info[-1])
        
        for i in range(5):
            case = list(combinations([0,1,2,3], i))
            for c in case:
                tmp = condition.copy()
                for idx in c:
                    tmp[idx] = '-'
                key = ''.join(tmp)
                d[key].append(score)
    
    for value in d.values():
        value.sort()
        
    for query in queries:
        query = query.replace("and ", "")
        query = query.split()
        # query = "java and backend and junior and pizza 100"일 때
        target_key = ''.join(query[:-1]) # "javabackendjuniorpizza"
        target_score = int(query[-1]) # 100
        count = 0
        if target_key in d:
            target_list = d[target_key]
            idx = bisect_left(target_list, target_score)
            count = len(target_list) - idx
        answer.append(count)
    
    return answer

굿 ~~