[프로그래머스] 순위 검색

---

문제설명

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

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

사고과정

• 처음에 너무 어려워서.. 질문하기 탭에서 어떤 분이 풀이 아이디어만 제공해주었는데, 이를 기반으로 머리싸매고 풀어보았다. 정확성에서는 다 맞았는데, 효율성에 모두 통과하지 못해서 내가 구현한 DFS 함수가 문제인가 싶어서 조합라이브러리를 사용해 바꾸었는데도 통과를 못했다.. 그래서 구글링에서 훌륭한 분의 풀이에 댓글로 질문을 하면서 이해할 수 있었다! 문제는 바로 hashmap의 value를 정렬할 때, 쿼리를 도는 Loop 안에서 해주었던 것... 이러지 말고 아예 쿼리를 돌기 전에 바깥에서 hashmap의 모든 value를 일중 loop로 정렬한 후, 쿼리를 도는 loop로 들어가면 에러가 발생하지 않는다...
• 조합 라이브러리를 사용하는 방법과 DFS를 통해서 조합 탐색을 활용한 풀이로 둘 다 풀어보았다.

풀이(스스로 못 푼 풀이)

- 조합 라이브러리 활용

from bisect import bisect_left, bisect_right
from itertools import combinations

def get_comb(info, hashmap):
    for i in info:
        i = i.split()
        i_key = i[:-1]
        i_val = int(i[-1])
        for j in range(5):
            for c in combinations(i_key, j):
                tmp_key = ''.join(c)
                if bool(hashmap.get(tmp_key)):
                    hashmap[tmp_key].append(i_val)
                else:
                    hashmap[tmp_key] = [i_val]
    return hashmap

def solution(info, query):
    hashmap = dict()
    
    hashmap = get_comb(info, hashmap)
    answer = []
    for key in hashmap.keys():
        hashmap[key].sort()
    for q in query:
        q = q.split(' ')
        q_score = int(q[-1])
        q = q[:-1]
        
        for i in range(3):
            q.remove('and')
        while '-' in q:
            q.remove('-')
        tmp_q = ''.join(q)
        
        if not bool(hashmap.get(tmp_q)):
            answer.append(0)
        else:
            scores = hashmap[tmp_q]
            left_idx = bisect_left(scores, q_score)
            count = len(scores) - left_idx
            answer.append(count)
            
    return answer

- DFS를 활용한 풀이

from bisect import bisect_left, bisect_right
from itertools import combinations
import copy


def get_dfs(info, hashmap):
    
    score = int(info.split(' ')[-1])
    info = info.split(' ')[:-1]
    res = copy.deepcopy(info)
    
    def dfs(L):
        if L == 4:
            key = ''.join(res)
            if bool(hashmap.get(key)):
                hashmap[key].append(score)
            else:
                hashmap[key] = [score]
            return
        else:
            res[L] = '-'
            dfs(L+1)
            res[L] = info[L]
            dfs(L+1)
    dfs(0)
    return hashmap
    
def solution(info, query):
    hashmap = dict()

    for i in info:
        hashmap = get_dfs(i, hashmap)
    # hashmap value 정렬
    for key in hashmap.keys():
        hashmap[key].sort()
        
    answer = []
    for q in query:
        target_score = int(q.split(' ')[-1])
        q = q.split(' ')[:-1]
        q = ''.join([x for x in q if x != 'and'])
        
        if not bool(hashmap.get(q)):
            answer.append(0)
        else:
            scores = hashmap[q]
            left_idx = bisect_left(scores, target_score)
            count = len(scores) - left_idx

            answer.append(count)
    return answer