안녕하세요 :)
https://programmers.co.kr/learn/courses/30/lessons/72412
2021 카카오 블라인드에서 출제되었던 순위검색 문제입니다.
풀이
점수를 제외한 언어~ 소울푸드 까지를 튜플로 만들어서 dict인 infos에 key로 저장합니다.
('java', 'backend', 'junior', 'chicken') 이런식으로요 !
이걸 키로해서 점수들을 넣어줍니다. 그럼 infos 는
{ ('java', 'backend', 'junior', 'pizza'): [150],
('python', 'frontend', 'senior', 'chicken'): [150, 210]......}
이런 형식이 됩니다.그럼 조건이 '-'이 아니라면 filter 메소드를 이용해 조건에 맞는 것으로 걸러줍니다.
이렇게 풀고나서 q_score 보다 크거나 같은 것들을 count해줍니다.여기서 !! 중요한점은 binary search를 통해 찾아야한단겁니다.
binary search를 이용하지 않으면 이 문제의 제약조건 때문에 시간초과가 납니다.
파이썬에서는 이분탐색 라이브러리인 bisect을 지원하므로 이걸 이용해서 간단하게 풀 수 있습니다.
import bisect
def solution(info, query):
ans = []
infos = {}
tmp = []
for item in info:
item = item.split()
k, score = tuple(item[:4]), int(item[-1])
tmp.append((k, score))
tmp.sort(key=lambda x: x[1])
for item in tmp:
k, score = item
if k not in infos:
infos[k] = []
infos[k].append(score)
for q in query:
q = q.split()
q = list(filter(lambda x: x != 'and', q))
q_score = int(q[-1])
q = q[:-1]
q_k = list(infos.keys())
for current_q in q:
if current_q == '-':
continue
q_k = list(filter(lambda x: current_q in x, q_k))
q_infos = [infos[x] for x in q_k]
q_result = 0
for scores in q_infos:
idx = bisect.bisect_left(scores, q_score)
count = len(scores) - idx
q_result += count
ans.append(q_result)
return ans