여러 경우의 수 중에서 주어진 score이상의 조건문에 부합하는 info의 수를 count하는 것이다.
query문중에 '-' 가 포함되어있는데 '-'는 조건문에 포함되지않는다.
따라서 "java backend junior pizza 150" 라는 info가 있으면 개발 언어, 직군, 경력 소울 푸드는 있거나 없을수도 있는 즉 2^4개로 16개의 다른 query에 부합한다고 볼 수 있다.
따라서 각 info마다 16개의 다른 info문을 만들어서 dictionary에 넣어놓는다. key값은 -를 없엔 string문이고 value값은 list안에 점수를 추가한다.
그리고 Lower bound를 구현하여 query와 dictionary와 value가 같은것 중에서 score가 같거나 높은 원소의 갯수를dictionary의 value에서 구한다.
기존의 데이터를 다른 형태로 가공하는 것.
이 문제에서는 info를 파싱해서 -를 삭제한 붙어있는 문자열 방식으로 파싱!
딕셔너리를 만드는 dict클래스의 서브 클래스
form collections import defaultdict 로 사용가능
인자로 주어진 객체의 기본값을 딕셔너리값의 초기값으로 지정가능
list_dict = defaultdict(list)
위와같이 설정하면 값을 지정하지 않은 키는 빈 list로([]) 지정된다.
'정렬' 된 배열에서 찾고자 하는 값 이상이 처음으로 나타나는 위치를 찾을때 사용된다.
같은 원소가 여러개 있더라도 상관이없다는 장점이있다.
이분 탐색 방법을 응용
list =[1,3,3,5,7,7,8] 의 숫자 배열이 있다고 할때 7이상의 위치를 찾으려고 할때
구간이 [0, len(list)] 이다.
구간의 중간위치를 m이라고 하면
list[m-1] <7 이면서 list[m] >= 7를 만족하는 최소 m를 찾으면 된다!
리스트를 탐색할때 7과 같거나 큰수가 나오는 첫 위치가 바로 lower bound이다.
from itertools import combinations
from collections import defaultdict
def solution(info, query):
answer = []
info_dict = defaultdict(list)
for infos in info:
temp = infos.split(" ")
key = temp[:-1]
score = int(temp[-1])
for i in range(5):
combi = list(combinations(key, i))
for c in combi:
temp_key = ''.join(c)
info_dict[temp_key].append(score)
for key in info_dict.keys():
info_dict[key].sort()
print(info_dict)
for querys in query:
querys = querys.split(" ")
query_key = querys[:-1]
query_score = int(querys[-1])
# print(query_key)
## and 는 최대 3개 까지 있다.
for _ in range(3):
query_key.remove("and")
while "-" in query_key:
query_key.remove("-")
##하나의 string으로 만든다.
query_key = ''.join(query_key)
if query_key in info_dict:
scoreList = info_dict[query_key]
# print(scoreList)
if len(scoreList) > 0:
left, right = 0, len(scoreList)
while left < right:
mid = (left + right) // 2
if scoreList[mid] >= query_score:
right = mid
else:
left = mid + 1
answer.append(len(scoreList) - left)
else:
answer.append(0)
# print(answer)
return answer
분명 프로그래머스 2레밸 문제라는데 어렵다..원래 2레밸이 이렇게 어려웠나 싶다...혼자 힘으로 못푼문제
combination이 많이쓰이는거 같도 lower bound도 중요하다.
파싱도 중요.. 중요한 요소가 엄청 많은 문제!!
복습 꼭많이하자