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

 

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

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

tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

 

 

문제 풀이

 

1. . 문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 됩니다.

예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.

2.  모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다.

3. 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.

4. 이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound 를 이용하면 됩니다.

 

 

"java backend junior pizza 150" 이와 같은 조건은 " - and backend and junior and pizza 150", "- and - and junior and - 100", "- and backend and - and pizza 80" 과 같은 모든 상황에서 검색되어야한다.

 

전체코드

from collections import defaultdict
from itertools import combinations

def solution(infos, queries):
    answer = []
    info_dict = defaultdict(list)
        
    for i in range(len(infos)):
        tmp = infos[i].split(" ")
        tmp_str, tmp_score = tmp[:-1], tmp[-1]
        
        for k in range(5):
            for combi in combinations(tmp_str, k): # 1. key = '-'를 제외한 모든 경우의 수 , value = tmp_score
                info_dict[''.join(combi)].append(int(tmp_score))
            
    for keys in info_dict:
        info_dict[keys].sort() # 2. key값에 따른 tmp_score오름차순으로 정리

    for query in queries:
        q = query.replace(" and ", "").replace("-", "") # 'and' 와 '-'를 제외한 query값
        q_str, q_score = q.split(" ") # 조건str 과 조건score로 나눔
        q_score = int(q_score) # 점수 int로 변환(중요)
        

        if q_str in info_dict: # 3. 만약 조건str이 info_dict에 있다면
            scores =info_dict[q_str]
            
            if scores: # 4. lower bound 실행 (이진탐색)
                start, end = 0 , len(scores)
                while start < end:
                    mid = (start + end) // 2
                    if scores[mid] >= q_score:
                        end = mid
                    else:
                        start = mid + 1
                
                answer.append(len(scores) - start) 
        
        else:
            answer.append(0)
    
    return answer

 

나머지 코드들은 거의 문자열을 처리해 주는 코드들이기 때문에, 문자열 처리에 익숙하다면 밑에 코드들만 보는 것이 이해가 쉬울 수도..

 

# 1. 모든조건이 상관없는 " - and - and - and - 100"과 같은 상황이 나올 수 있으므로 " ": [100] 과 같은 빈문자열 key 값(k = 0) 도 만들어주어야 한다.

for k in range(5):
   for combi in combinations(tmp_str, k): 
       info_dict[''.join(combi)].append(int(tmp_score))

# 2. query문 조건 점수 '이상'을 가진 지원자를 찾아야 하므로, 정렬을 하면 나중에 시간을 단축할 수 있다.

for keys in info_dict:
     info_dict[keys].sort()

# 3. 이 때, scores는 해당 조건을 가진 점수들의 list

if q_str in info_dict: 
    scores =info_dict[q_str]

 

# 4. lower bound를 파이썬 라이브러리를 불러와 실행해주면 훨씬 간단하다.

from bisect import bisect_left

if scores:
    answer.append(len(scores) - bisect_left(scores, q_score))