[프로그래머스] 카카오기출 / 순위검색 / python

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

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

 

🤔접근방법

1. dict로 info를 저장하고 query를 돌면서 query의 각 요소가 dict[key]에 모두 포함되어 있는지 확인하며 풀었더니 for문 중첩이 너무 심해져서 정확성만 통과하고 효율성은 통과하지 못했다.

2. 처음에 모든 경우의 수를 dict에 저장하고 query의 key값을 바로 대입함과 동시에 이진탐색으로 조건에 맞는 점수 갯수를 구해야하는 문제였다.

요런 자료구조를 만들어야함! 출처 : https://www.youtube.com/watch?v=izxzh0rQxSI  

3. 즉 하나의 info 정보를 통해 매칭될 수 있는 모든 경우의 수에다가 점수를 추가해주는 것이다. 

   ex) 'java backend junior pizza' 이라면 'java backend junior -', 'java backend - pizza', 'java - junior pizza', '- backend junior pizza', '- - junior pizza', '- backend - pizza' ..... 등등 모든 경우의 수를 표시해준다.

이런 느낌! (모든 경우의 수 표기)

4. 그리고 query정보를 돌면서 상응하는 key값의 score_list를 찾고 그 곳에서도 이진탐색을 통해 조건에 맞는 score 갯수를 구해야 효율성까지 통과할 수 있다.

 

🔥코드구현

from collections import defaultdict

def solution(info, query):
    score_dict = defaultdict(list)
    answer = [0] * len(query) 
    for i in range(len(info)):
        A, B, C, D, score = info[i].split()
        score = int(score)
        A_list = [A, '-']
        B_list = [B, '-']
        C_list = [C, '-']
        D_list = [D, '-']
        for q in range(2):
            for w in range(2):
                for e in range(2):
                    for r in range(2):
                        name = A_list[q] + B_list[w] + C_list[e] + D_list[r]
                        score_dict[name].append(score)
        print(score_dict)
    
    for key in score_dict.keys():
        score_dict[key].sort()
    
    for i in range(len(query)):
        query_list = list(query[i].split())
        score = int(query_list.pop(-1))
        for _ in range(3):
            query_list.remove('and')
        
        Q = "".join(query_list)
        
        score_list = score_dict[Q]
        if len(score_list) > 0:     
            left = 0
            right = len(score_list)
            while left < right:
                mid = (left + right) // 2
                if score_list[mid] >= score:
                    right = mid
                else:
                    left = mid+1
            answer[i] = len(score_list) - left
        else:
            answer[i] = 0
                
    return answer