[프로그래머스] Lv.2 순위 검색 [Python, 파이썬] KAKAO

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/72412
• 🔑 경우의 수 구하기, 이분탐색
  • 핵심 1
    • info 요소가 "java backend junior pizza 150" 일 때
    • 먼저 점수는 따로 분리해서 저장한다. (150)
    • "java backend junior pizza" 문자열이 쿼리에 포함될 수 있는 경우를 모두 구한다. (총 16가지)
    • ex) "java backend junior pizza", "- backend junior pizza", "java - junior pizza", ㆍ ㆍ ㆍ  , "- - - -" 까지
    • { "javabackendjuniorpizza" : [150], "-backendjuniorpizza" : [150], ㆍ ㆍ ㆍ , "- - - -" : [150] }
      • 모든 info 요소를 딕셔너리에 이런 형태로 추가한다. (문자열은 공백을 모두 제거함)
      • 쿼리가 겹치는 경우가 있을 수 있으니 점수 리스트에 append를 해야 한다.
        • "- backend junior pizza 100" 이 쿼리에는
        • "python backend junior pizza 150", "cpp backend junior pizza 200" 둘 다 포함되기 때문이다.
  • 딕셔너리를 완성했으면 딕셔너리 value인 점수 리스트들을 오름차순 정렬을 해준다.
    • 처음에는 쿼리문을 반복하는 과정 안에서 쿼리에 해당하는 점수 리스트들을 불러와서 정렬하니까 시간초과 났다.
    • 그래서 쿼리문 들어가기 전 딕셔너리에 모든 점수 리스트들을 정렬했다.
    • 이 부분도 거의 핵심
  • 핵심 2
    • 쿼리 되는 문자열도 딕셔너리의 key값에 맞게 전처리한다.
    • 쿼리에 해당하는 점수 리스트를 불러온다.
    • 이 리스트에서 이분 탐색을 통해 쿼리 하는 점수 이상인 인덱스를 찾는다.
    • (리스트 길이 - 인덱스)를 정답 리스트에 추가한다.
  • 끝 ✨

 

from itertools import combinations
from collections import defaultdict
import re

def solution(info, query):
    answer = []
    
    info_dict = defaultdict(list)
    comb = []
    for i in range(1, 5):   # '-' 집어넣을 경우의 수 생성
        for j in combinations([0, 1, 2, 3], i):
            comb.append(j)
    
    for s in info:
        score = re.search('\d*$', s).group()        # 점수 추출
        s = re.sub(score, '', s).split()            # 문자열에서 점수 제거
        info_dict["".join(s)].append(int(score))    # 'javabackendjuniorpizza': [150]
        
        for c in comb:                              # 문자열에 '-' 로 변환 작업 (쿼리에 만족하는 경우의 수)
            tmp = list(s)                           # 리스트 깊은 복사
            for i in c:
                tmp[i] = '-'
            info_dict["".join(tmp)].append(int(score))

    for i in info_dict:                             # 점수 리스트들을 오름차순 정렬
        info_dict[i].sort()
            
    for q in query:
        score = re.search('\d*$', q).group()        # 점수 추출
        q = re.sub(' ' + score, '', q)              # 문자열에서 ' 점수' 제거
        q = re.sub(' and ', '', q)                  # 문자열에서 ' and ' 제거
        
        score_list = info_dict[q]                   # 쿼리에 해당하는 점수가 들어있는 리스트

        l, r = 0, len(score_list)-1                 # 점수 리스트에서 쿼리 점수 이상인 인덱스를 이분탐색으로 찾기
        
        while l <= r:                               # 이분탐색
            mid = (l+r) // 2
            
            if int(score) <= score_list[mid]:
                r = mid - 1
            else:
                l = mid + 1
        answer.append(len(score_list) - l)
                 
    return answer