문제
문제 해설
주어진 query에 따라 해당 점수 이상인 사람이 몇명인지 찾는 문제입니다.
정확성과 효율성 테스트를 모두 통과해야 하므로 효율적인 알고리즘을 써야합니다.
정확성 테스트같은 경우에는 주어진 쿼리에 따라 info를 완전 탐색하면 통과할 수 있습니다. 하지만 1 <= info <= 50,000, 1 <= query <= 100,000이므로 효율성 테스트를 통과할 수 없습니다.
효율성 테스트를 통과하기 위해 세그먼트 트리나 트라이 알고리즘과 같은 트리 구조를 생각했으나 중간에 "-"가 끼어 있는 비효율적인 상황이 발생할 수 있어 역시 효율성 테스트를 통과할 수 없다고 생각했습니다.
풀이 방법
풀이 방법은 주어진 info를 딕셔너리에 key로 넣을 수 있게 알맞게 전처리한 뒤, value 값으로 점수를 리스트 형식으로 쌓아가는 방식입니다.
위와 같이 검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다. 따라서 모든 조건에 부합하는 key 값을 찾아 딕셔너리에 저장해야 합니다.
포인트는 "-"를 처리하는 것인데, 첫번째로 해야하는 것은 위 4자리에 "-"를 조합을 통해 자리를 선정한다입니다.
그렇게 key-value를 저장한 뒤, 이분 탐색을 사용하기 위해 모든 value(리스트)값을 정렬 해야합니다.
마지막으로 query를 통해 조건을 딕셔너리에서 찾고 이분탐색을 value의 리스트에서 하면 됩니다.
풀이 코드
from itertools import combinations
import bisect
import re
def solution(info, query):
answer = []
d = {}
# 1. info 전처리 후 딕셔너리에 저장
for s in info:
l = list(map(str, s.split()))
value = l.pop()
for i in range(5):
# 조합으로 4자리 중 '-' 가 들어갈 자리를 선정.
for com in combinations([i for i in range(4)], i):
string = ""
for k in range(4):
if k in com:
string += "-"
else:
string += l[k]
# 딕셔너리에 key - value 저장
d.setdefault(string, [])
d[string].append(int(value))
# 2. 딕셔너리 모든 값 정렬
for x in d.keys():
d[x].sort()
# 3. query 전처리 후 딕셔너리에서 value를 꺼내 이분 탐색
for s in query:
l = re.findall(r"\b(?!and\b)\w+|[-]", s)
value = int(l.pop())
string = "".join(l)
if d.get(string) == None:
answer.append(0)
else:
# 값이 존재한다면 이분 탐색으로 값을 찾는다.
idx = bisect.bisect_left(d[string], value)
# 해당 되는 사람이 없음
if idx == len(d[string]):
answer.append(0)
# 그게 아니면 idx부터 끝까지 count
else:
answer.append(len(d[string]) - idx)
return answer