[문제]
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
- info 배열의 크기는 1 이상 50,000 이하입니다.
- info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
- 개발언어는 cpp, java, python 중 하나입니다.
- 직군은 backend, frontend 중 하나입니다.
- 경력은 junior, senior 중 하나입니다.
- 소울푸드는 chicken, pizza 중 하나입니다.
- 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.
- query의 각 문자열은 "[조건] X" 형식입니다.
- [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
- 언어는 cpp, java, python, - 중 하나입니다.
- 직군은 backend, frontend, - 중 하나입니다.
- 경력은 junior, senior, - 중 하나입니다.
- 소울푸드는 chicken, pizza, - 중 하나입니다.
- '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
[입출력 예]
info query result ["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"] ["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"] [1,1,1,1,2,4]
concept
-
4가지 query가 나옴.. and로 구분되어 있음(추후에 인덱스설정으로 and로 구분x)
-
해당하는 query에 만족하는 인원을 뽑아내야하는데,, 효율성 문제가 있으므로.. 바로 찾을 수 있어야함.
-
각 쿼리의 경우에 지원자의 점수를 (중복으로) 저장하여 찾는다.
-
각 쿼리로 나올 수 있는 경우의 수 = 4(개발언어+'-') 3(직군+'-') 3(경력+'-') * 3(푸드+'-') = 108가지..
-
108가지의 배열에 해당 점수들을 저장해서 질의에 해당하는 인원수를 찾아야 한다.
-
각각의 배열에 개별 query로 인덱스 접근이 가능해야하므로,, 인덱싱을 위하여 개별 번호를 부여해줘야함.
ex) python(2)(3x3x3) and backend(1)(3x3) and senior(2)x3 and pizza(1)
ex) 모든 조건이 없는 경우 = 0 + 0 + 0 + 0 = 0 인덱스..
ex) 모든 조건이 있는 경우 = 3x(3x3x3) + 2x(3x3) + 2x3 + 2 = 107인덱스.. -
각각의 질문에,, 해당 안되는 사항들을 저장해줘야하기때문에, 부분집합을 활용한다.
-
하나씩 포함이 안되는 경우로,, bit연산 활용 (부분집합이므로..)
Code
#이분법 탐색
from bisect import bisect_left
def solution(info, query):
answer = []
hashmap={'-':0,
'cpp':1, 'java':2,'python':3,
'backend':1, 'frontend':2,
'junior':1, 'senior':2,
'chicken':1, 'pizza':2}
#점수가 들어갈 배열..
scores = [[] for _ in range(4*3*3*3)]
for data in info:
st = data.split()
#해당 데이터는 '-'의 상황도 저장해야하므로, 부분집합..!
arr = (hashmap[st[0]]*3*3*3,
hashmap[st[1]]*3*3,
hashmap[st[2]]*3,
hashmap[st[3]])
score = int(st[4])
#부분집합의 원소의 개수 4개 -> 16가지 경우
for i in range(1<<4):
idx = 0
# 부분집합에 불이 켜진 경우
for j in range(4):
if i & (1 << j):
idx += arr[j]
scores[idx].append(score)
for i in range(4*3*3*3):
scores[i].sort()
for string in query:
q = string.split()
idx = hashmap[q[0]]*3*3*3 + hashmap[q[2]]*3*3 +hashmap[q[4]]*3 + hashmap[q[6]]
score = int(q[7])
#score보다 크거나 같은 원소가 몇개 있는지..!
answer.append(len(scores[idx]) - bisect_left(scores[idx],score))
return answer참고
- 예전, quickSorting에서 피벗을 기준으로 몇번째 큰 수 인지 확인하는 방법이 있었는데 파이썬에서는 bisect라는 라이브러리가 있었다..!
- bisect_left -> 같은 값일 때, 왼쪽으로,,
- bisect_right -> "" , 오른쪽으로,,
- 효율성을 고려하여 매번 해당하는 원소들을 반복순회하여 찾기보단,, 메모리를 조금 더 사용하여 데이터에 접근하는 것이 더 효율적이다
- 약간 hashing처럼 접근하여 사용하므로 탐색시간은 굉장히 빠를 것.
- 포함이 안되는 경우의 hashing값을 0 으로 설정하여 부분집합으로 탐색..!
