Programmers#순위 검색

LEVEL :

Level2

문제 요약 :

2021년 카카오톡 코딩테스트 제출 문제이다.

문자열로 주어진 값들을 잘 처리하여 쿼리에 대한 질문을 정확하고 효율적이게 처리하는 문제임

해결 방안 :

처음에 든 생각은 2가지 였다. set로 각 영역을 intersection시키는 방법 하나, dictionary에 info 값을 잘 처리하여 key값으로 넣는 방법 하나 이렇게 총 두가지이다. 처음으로 set으로 해결은 무척 간단 했고 정확성은 100프로 였지만 효율성 측면에서 통과하지 못하여 결국 dictionary를 사용하는 법으로 넘어갔다. 처음에는 dictionary에 info에서 주어진 값들만을 집어넣었다. 예를들어 미리 lang = {"java" : "1" , "python" :"2"} ,food = {
"chicken":"1","pizza":"2"},..등등 이렇게 미리 구현해 두어 info 값을 1212와 같은 key 값으로 만들어 해당영역에 포함하는 점수들을 list로 저장해두었다. 그런데 이렇게 하니 추후에 "-"와 같은 문제를 해결해야 했고 처리하기도 굉장히 귀찮아져 그냥 {java,pizza,...}를 조합으로 "-"는 ""으로 치고 다 경우의 수를 구하니 하나의 키값당 16가지 경우의 수가나온다. 그 후 query에 대한 값으로 영역에 포함하는 모든 점수들의 list값을 다 불러올수있었고 이를 이분탐색으로 logN 속도로 탐색이 가능했다.
꽤나 어려웠던 문제였던 것 같다.

Solution1 - set intersection 사용 -> 효율성 실패

import re

def findCount(num,arr) :
    cnt = 0
    for i in range(len(arr)) :
        if num <= arr[i][1] :
            cnt+=1
    return cnt
def solution(info, querys):
    res = []
    lang = {"cpp":[],"java":[],"python":[],"-":[]}
    job = {"backend":[],"frontend":[],"-":[]}
    career = {"junior":[],"senior":[],"-":[]}
    food = {"chicken":[],"pizza":[],"-":[]}
    
    info = [list(info[i].split()) for i in range(len(info))]
    querys = [list(re.split(" and | ",querys[i])) for i in range(len(querys))]

    for i in range(len(info)) :
        uid = i
        user_score = int(info[i][4])
        lang[info[i][0]].append((uid,user_score))
        lang["-"].append((uid,user_score))
        job[info[i][1]].append((uid,user_score))
        job["-"].append((uid,user_score))
        career[info[i][2]].append((uid,user_score))
        career["-"].append((uid,user_score))
        food[info[i][3]].append((uid,user_score))
        food["-"].append((uid,user_score))
        
    for query in querys :
        intersection = list(set(lang[query[0]]) & set(job[query[1]]) & set(career[query[2]]) & set(food[query[3]]))
        res.append(findCount(int(query[4]),intersection))
        return res

Solution2 - 모든 경우를 미리 구해두고 bs탐색

from itertools import combinations 

def findCount(arr,num) :
    arr_len = len(arr)
    if arr_len > 0 :
        left,right = 0,len(arr)
        while left < right:
            mid = (left + right) // 2
            if num > arr[mid]:
                left = mid + 1
            else:
                right = mid 
    return arr_len-left
def solution(info, querys):
    res = []
    dic = {}
    for info_list in info :
        query = info_list.split()
        dic_key = query[:-1]
        score = int(query[-1])
        for i in range(5) :
            for key in combinations(dic_key, i) :
                    new_pattern = ''.join(key)
                    if new_pattern in dic :
                        dic[new_pattern].append(score)
                    else:
                        dic[new_pattern] = [score]
                    
    for i in dic :
        dic[i].sort()

    for query in querys :
        query = query.split()
        score = int(query[-1])
        key = "".join(query[:-1]).replace("-","").replace("and","").replace(" ","")
        if key in dic :
            res.append(findCount(dic[key], score))
        else :
            res.append(0)
    return res

출처

프로그래머스 : https://programmers.co.kr/learn/courses/30/lessons/72412