반응형
programmers.co.kr/learn/courses/30/lessons/72412
코딩테스트 연습 - 순위 검색
["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","pyt
programmers.co.kr
from itertools import combinations
from collections import defaultdict
from bisect import insort, bisect_left
def solution(info, query):
answer = []
allCases = defaultdict(list) # {info에 따라 구성될 수 있는 query 조합 : [점수]}
for i in info:
i = i.split()
for j in range(1, 5):
for comb in combinations(i[:-1], j): # 점수를 제외한 항목들의 모든 부분집합
insort(allCases[''.join(comb)], int(i[-1])) # 정렬된 상태로 점수 추가
insort(allCases[''], int(i[-1])) # 모든 항목이 상관 없을 경우 key를 ''으로 하여 점수 추가
for q in query:
q = q.replace('and', '').replace('-', '').split() # 문자열 처리
idx = bisect_left(allCases[''.join(q[:-1])], int(q[-1])) # 현재 query의 점수 위치 index
# 해당 조건(key)에 맞는 value 개수 - 현재 점수가 들어갈 수 있는 index = 현재 점수 보다 높은 점수 개수
answer.append(len(allCases[''.join(q[:-1])]) - idx)
return answer→ Level 2 문제여서 효율성이 있는지 확인도 안하고 greedy하게 풀었다가 크게 돌아갔다.
이게 왜 Level 2...
처음 통과한 코드는 insort 대신 query 탐색 이전에 모든 allCases를 정렬해주고,
query 탐색 반복문에서 이분탐색 직접 구현했었다.
bisect 모듈을 한 번도 안써봤는데 공부할겸 찾아서 적용해보았음. 앞으로 자주 사용해야겠다.
반응형