[문자열, 이진탐색] 프로그래머스 순위 검색 Python

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

※ 정확성(O), 효율성(O) 풀이

이진탐색 이용

from itertools import combinations
from collections import defaultdict # 키 존재 여부 확인X

def binarySearch(dic, target): # Lower Bound(점수 몇 점 이상)
    ans = 0
    s = m = 0
    e = len(dic)-1
    while s <= e:
        m = int((s+e)/2) # int 함수 조심
        
        if dic[m] >= target:
            ans = max(ans, m+1) # 최댓값 저장
            s = m + 1
        else:
            e = m - 1
    
    return ans
    

def solution(info, query):
    answer = []
    dic = defaultdict(list)

    for i in info:
        tempI = i.split(" ")
        for cnt in range(5):
            for l in list(combinations(tempI[:-1],cnt)):
                dic["".join(l)].append(int(tempI[4])) # 문자열 키
    
    for v in dic.values():
        v.sort(reverse = True) # 내림차순(정렬X 시간초과)
    
    for q in query:
        tempQ = q.replace(" and ", " ").replace("-","").split(" ")
        tempL = dic["".join(tempQ[:-1])]
        answer.append(binarySearch(tempL, int(tempQ[4])))
    
    return answer

 

※ 정확성(O), 효율성(X) 코드

50,000 X 100,000 = 5,000,000,000(50억) 연산 횟수

def solution(info, query):
    answer = []

    for q in query:
        cnt = 0
        for i in info:
            tempI = i.split(" ")
            tempQ = q.replace(" and ", " ").split(" ")
            
            for idx in range(4):
                if tempQ[idx] == '-':
                    tempQ[idx] = tempI[idx]
            
            if tempI[0:4] == tempQ[0:4]:
                if int(tempI[4]) >= int(tempQ[4]):
                    cnt += 1 # answer[query.index(q)] += 1 # 쿼리 겹칠수 있음(unique X)
        answer.append(cnt)
    
    return answer