문제분석
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
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"]
result = [1,1,1,1,2,4]
지원자 정보가 info 배열에 저장되며, 쿼리 정보가 query 배열에 저장된다.
query 중 조건이 없는 경우 - 로 표시된다.
지원자 중 query 조건에 맞는 수를 결과에 담아 반환
아이디어
query 중간 조건이 없는 경우도 존재하므로 info의 모든 조합을 고려해야함.
info의 모든 조건에 대해
딕셔너리 만들어서 지원자의 모든 info 조합을 key로 하고 그 안에 score를 value로 저장.
딕셔너리의 모든 원소 정렬.
query에 맞는 key에서 이진탐색으로 특정점수 넘는 지원자 수 확인
코드
from itertools import combinations
from bisect import bisect_left
def solution(info, query):
d = dict()
for val in info:
val = list(val.split()) #info를 list로 저장.
score = int(val[-1]) #점수는 따로 뺌. value로 저장하기 위해
val = val[:-1] #key로 사용할 info정보 리스트.
# 모든 조합에 대해 key를 생성하는 과정
for i in range(5): #info의 조건 4가지. 0~4까지 뽑을 수 있게.
for c in combinations(val, i):
temp = ""
for v in c:
temp += v #만든 조건을 붙인 문자열 생성
if temp in d: #이미 해당 키값 있다면 점수 삽입
d[temp].append(score)
else:
d[temp] = [score]
#이진 탐색 위해 정렬
for v in d.values():
v.sort()
#쿼리 탐색
answer = []
for val in query:
val = list(val.split())
q = "" #찾는 key로 사용할 문자열
target_score = int(val[-1]) #찾는 점수
for i in range(len(val) - 1):
if val[i] != "-" and val[i] != "and":
q += val[i]
if q not in d: #해당 key가 없다면 0 삽입
answer.append(0)
else: #있다면 bisect_left로 정렬 유지한채로 어디에 삽입할지 위치확인
v = bisect_left(d[q], target_score)
answer.append(len(d[q]) - v) #상위 개수 결과에 삽입
#찾는 점수 이상이므로 해당 점수도 포함. 따라서 bisect_left.
return answer분석
모든 info에서 0개 ~ 4개 선택하는 경우를 combinations으로 구한 뒤. 문자열을 이어붙여 key로 만들고. 해당 key에 score 삽입.
query도 마찬가지로 문자열을 이어붙여 key로 만들고. 해당 key에서 이진탐색 수행.
query에 해당하는 것이 하나도 없다면 0 삽입하는 것에 유의.
시간복잡도 줄이기 위해 탐색이 O(1)인 dictionary를.
중복된 key에서 탐색 속도를 줄이기위해 이진탐색용 라이브러리인 bisect 사용.
