문제 설명
쿼리에 들어온 문자열에 따라 해당되는 지원자의 숫자의 배열을 결과로 반환해주면 된다.
지원자들의 조건은 언어, 직군, 경력, 소울푸드, 코테점수로 나뉜다.
- 언어는 cpp, java, python 중 하나
- 직군은 backend, frontend 중 하나
- 경력은 junior, senior 중 하나
- 소울푸드는 chicken, pizza 중 하나
쿼리는 언어, 직군, 경력, 소울푸드, 코테점수를 각각 and를 사이에 두고 들어오게 되고, 쿼리의 마지막에는 코테점수가 들어오게 된다.
코테점수 이상이고, 쿼리 조건에 맞는 지원자의 수를 구해야 한다.
이때 코테점수를 제외한 나머지 쿼리에는 '-'가 들어올수 있는데 이는 해당 조건을 고려하지 않겠다는 뜻이다.
예를들어 "cpp and - and senior and pizza 500" 이라는 쿼리가 들어오게 되면 언어는 cpp, 경력은 senior, 소울푸드는 pizza를 선택한 지원자중 점수가 500점 이상인 지원자의 수를 계산해 반환해주면 된다.
풀이 과정
첫번째 시도
처음에는 일단 info 와 query를 split으로 구분해서 조건에 맞는 지원자를 찾을수 있게 만든 후에 info를 순회하면서 알맞는 지원자의 수를 구해보려고 하였다.
그러나 이 문제는 정확성 뿐 아니라 효율성도 점수가 있는 문제여서 이를 해결하기위해 info를 split으로 구분해준 다음 점수를 기준으로 정렬을 해서 점수부터 검사하고 query의 점수보다 낮은 지원자가 나오면 바로 지원자 수를 result에 넣어주는 방식으로 최적화를 진행하였다.
def solution(info, query):
answer = []
people = sorted([i.split(' ') for i in info], key= lambda x : -int(x[4]))
q = [i.split(' ') for i in query]
for i in q:
count = 0
for person in people:
if (int(i[7]) > int(person[4])): break
if ((i[0] == person[0] or i[0] == '-') and (i[2] == person[1] or i[2] == '-') and
(i[4] == person[2] or i[4] == '-') and (i[6] == person[3] or i[6] == '-')): count += 1
answer.append(count)
return answer어느정도 최적화를 해주었다고 생각했지만 문제는 그렇게 간단하게 풀리지 않았다.
채점 결과
정확성: 40.0
효율성: 0.0
합계: 40.0 / 100.0정확성에서는 만점을 받았지만 효율성에서는 단 1점도 얻지 못하였다.
두번째 시도
info 배열의 조건을 점수를 이용하여 최적화를 해주었지만 어쨌든 info 배열의 지원자를 한명씩 검사하는 방식이기에 효율성 점수가 안나온다고 판단하여 dict를 사용해 최적화를 해주어야겠다고 생각했다.
지원자의 정보를 한명씩 쿼리와 검사하는게 아닌 지원자의 정보를 가지고 가능한 모든 쿼리의 경우의 수를 미리 dict에 넣어놓으면 나중에 쿼리를 가지고 검사를 할때 점수만 가지고 몇명인지 판단이 가능하다.
예를들어 java backend junior pizza 150라는 지원자가 들어오면 해당 지원자를 검사해야하는 모든 쿼리의 경우의 수를 미리 dict에 저장해놓는것이다.
위의 예시에서는 다음과 같은 16가지의 key값에 해당 지원자의 점수가 저장될것이다.
이러한 방식으로 미리 dict에 지원자의 점수를 저장해두고, 나중에 쿼리가 들어오면 해당 쿼리를 dict에 넣어서 유효한 점수를 가진 지원자만 찾으면 된다.
지원자의 수를 찾는 방식은 이분탐색을 이용하였고, 해당 점수를 가진 지원자가 없을수도 있으므로 lower bound를 이용하여 해당 점수보다 최초로 같거나 큰 인덱스를 찾아주었다.
최종 코드
def solution(info, query):
answer = []
db = {}
for lang in ['cpp', 'java', 'python', '-']:
for position in ['backend', 'frontend', '-']:
for year in ['junior', 'senior', '-']:
for food in ['chicken', 'pizza', '-']:
db.setdefault((lang, position, year, food), [])
for i in info:
i = i.split(' ')
for lang in [i[0], '-']:
for position in [i[1], '-']:
for year in [i[2], '-']:
for food in [i[3], '-']:
db[lang, position, year, food].append(int(i[4]))
for key in db:
db[key].sort()
for q in query:
q = q.split(' ')
data = db[(q[0], q[2], q[4], q[6])]
target = int(q[7])
left = 0
right = len(data)
while left < right:
mid = (left + right) // 2
if data[mid] >= target:
right = mid
else:
left = mid + 1
answer.append(len(data) - left)
return answer결과
Link
