문제정리
https://programmers.co.kr/learn/courses/30/lessons/72412
query의 조건에 맞는 info의 원소 수를 리스트에 담아 반환하면 되는 문제입니다.
입출력 예
| 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] |
문제풀이
구현에 대한 아이디어는 간단해보였습니다.
파싱
query의 "and "를 제거 후 공백을 기준으로 나눕니다.
info 또한 공백을 기준으로 나눕니다.
비교
반복문으로 단순 비교하는 방식
우선 점수를 비교하여 작다면 다른 조건을 보지 않습니다.
query의 조건이 "-"가 아니라면 비교하게 됩니다.
두 값이 같지 않다면 flag는 False가 되고 반복문을 빠져나옵니다.
flag의 True, False 여부로 count를 증가시킨 후 해당 count값을 결과 answer 리스트에 추가하는 식으로 구현했습니다.
def solution(info, query):
answer = []
for q in query:
q = q.replace("and ", "")
q = q.split()
count = 0
for i in info:
i = i.split()
flag = True
if int(i[4]) < int(q[4]):
flag = False
else:
for idx in range(4):
if q[idx] == "-":
continue
else:
if q[idx] != i[idx]:
flag = False
break
if flag:
count += 1
answer.append(count)
return answer정확성 통과, but 효율성 실패!
정확성은 통과하지만 효율성에서 막혔습니다.
결국 카카오 문제 풀이를 참고했습니다...
시간초과 해결
https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
예를 들어 “java backend junior pizza 150” 의 경우 위와 같이 16가지 경우에 검색이 됩니다.
key는 16개의 경우의 수, value는 score를 넣어 해쉬를 이용해 검색하는 Dictionary를 만듭니다.
검색 시 조건을 key 값으로 넣는다면 해당 value, 즉 점수 리스트를 얻을 수 있습니다.
여기서 특정 점수 이상의 수를 찾기 위해 하나씩 비교하여 찾는다면 데이터가 많으면 많을 수록 시간이 많이 소모될 것 입니다.
정렬된 데이터에서의 빠른 검색이 특징인 이분 탐색(Binary Search)을 이용하면 빠르게 결과를 얻을 수 있습니다.
이 때, 배열에 해당 값이 없을 수도 있으므로 배열에서 해당 값보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 합니다.
이는 Lower Bound를 이용하면 됩니다.
이분 탐색, Lower Bound, 그리고 Upper Bound
이분 탐색이 '원하는 값을 찾는 과정' 이라면 Lower Bound는 '원하는 값 이상이 처음 나오는 위치를 찾는 과정' 이며, Upper Bound는 '원하는 값을 초과한 값이 처음 나오는 위치를 찾는 과정'입니다.
파이썬 bisect 라이브러리의 bisect_left는 lower bound
bisect 라이브러리 이용한 코드
from itertools import combinations
from collections import defaultdict
from bisect import bisect_left
def solution(information, queries):
answer = []
dic = defaultdict(list)
for info in information:
info = info.split()
condition = info[:-1]
score = int(info[-1])
for i in range(5):
case = list(combinations([0,1,2,3], i))
for c in case:
tmp = condition.copy()
for idx in c:
tmp[idx] = "-"
key = ''.join(tmp)
dic[key].append(score)
for value in dic.values():
value.sort()
for query in queries:
query = query.replace("and ", "")
query = query.split()
target_key = ''.join(query[:-1])
target_score = int(query[-1])
count = 0
if target_key in dic:
target_list = dic[target_key]
idx = bisect_left(target_list, target_score)
count = len(target_list) - idx
answer.append(count)
return answer
Lower Bound 구현 코드
from itertools import combinations
from collections import defaultdict
def lower_bound(begin, end, target_list, target):
if begin >= end:
return begin
mid = (begin + end) // 2
if target_list[mid] >= target:
return lower_bound(begin, mid, target_list, target)
else:
return lower_bound(mid+1, end, target_list, target)
def solution(information, queries):
answer = []
dic = defaultdict(list)
for info in information:
info = info.split()
condition = info[:-1]
score = int(info[-1])
for i in range(5):
case = list(combinations([0,1,2,3], i))
for c in case:
tmp = condition.copy()
for idx in c:
tmp[idx] = "-"
key = ''.join(tmp)
dic[key].append(score)
for value in dic.values():
value.sort()
for query in queries:
query = query.replace("and ", "")
query = query.split()
target_key = ''.join(query[:-1])
target_score = int(query[-1])
count = 0
if target_key in dic:
target_list = dic[target_key]
idx = lower_bound(0, len(target_list), target_list, target_score)
count = len(target_list) - idx
answer.append(count)
return answer
