[2021 kakao / 프로그래머스] 72412번 : 순위 검색

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/72412

 

문제 이해 

각 query의 조건을 만족하는 info에서의 지원자 수를 각각 담아서 출력하는 문제다.

이해를 바탕으로 매 query에 대해서 모든 info를 탐색하면서 맞는 지원자 수를 세는 로직으로 했는데 모든 효율성 테스트에서 실패했다. 

그래서 구글링을 해봤더니 딕셔너리와 이진탐색을 이용하면 된다. 

 

풀이 이해

• java backend junior pizza 150의 경우 해당되는 조건은 각 (단어 + '-', 총 두 개)로 언어, 직무, 경력, 음식 총 4번 카운트하면 16개의 경우의 수가 있다. (예 : 조건이 - backend - pizza 100인 경우도 해당 지원자가 만족하는 조건이다.)
• 그렇기에 지원자의 정보에 해당하는 경우들을 key로 만든다음 그 조건을 만족하는 지원자들의 코테 점수를 value에 리스트로 저장하면 된다. 
• query에 해당하는 조건이 딕셔너리 키에 있을 때, 해당 조건의 점수 리스트에서 타겟 점수 이상인 인덱스를 이진탐색으로 구하면 해당 인덱스부터 끝까지의 원소 개수가 해당 query 조건을 모두 만족하는 지원자 수이므로 그를 answer에 추가하면 된다. 
  • 풀이에서 bisect_left를 사용하는 이유 : value를 오름차순 정렬하므로 조건을 만족하는 점수가 처음 나오면 그 값의 인덱스부터 마지막 인덱스까지는 모두 타겟 점수를 만족하는 숫자들이다. 그렇기에 왼쪽 인덱스가 오른쪽으로 움직이면서(인덱스가 작은 값이 큰 값으로) 진행돼야하기 때문이라고 생각한다. 

 

- 정답 풀이 :

 

풀이에서 배운 것들 

• 지원자 정보로 만들 수 있는 모든 경우 구하기 위해서 combinations이용해서 '-' 추가할 위치 임의로 구한다
• 기존의 condition을 copy()한 temp를 만들어서 조합 위치에 '-'로 바꾼다 
• key에는 리스트 대신 문자열을 위치시킬 것이므로 ''.join(temp)를 한다 
• 각 query의 and를 ' '로 대체한 뒤, 모든 ' '(띄어쓰기)를 기준으로 단어를 분리한다
• 분리한 단어들로 다시 하나의 문자열로 변경한다  

참고한 블로그

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

 

 

- 시도해본 풀이 :

정확성은 다 맞았는데 효율성 테스트는 통과하지 못했다.

query가 최대 5만이고, info가 최대 10만이라서 최대 시간 복잡도가 50억이라서 이를 고려한 코드를 짜지 않아서 그런 것 같다 

빠르게 조회할 수 있도록 최적화가 필요한 것 같다 

def solution(info, query):
    people = []
    for i in info:
        people.append(i.split(' '))
        
    for i in range(len(query)):
        query[i] = query[i].split(' ')  
        query[i].append(i)
       
    people.sort()
    query.sort()
    answer = [0] * len(query)
    for i in range(len(query)):
        number = 0
        temp = [query[i][0], query[i][2], query[i][4], query[i][6], query[i][7]]
        for j in range(len(people)):
            count = 0
            for k in range(5):
                if temp[k] == '-':
                    count += 1
                else:
                    if k == 4:
                        if int(temp[k]) > int(people[j][k]):
                            continue
                    elif temp[k] != people[j][k]:
                        continue
                    count += 1
            if count == 5:
                number += 1
                                  
        answer[query[i][-1]] = number 
        
    return answer

700