[프로그래머스] 72412번 문제 2021 KAKAO BLIND RECRUITMENT 순위 검색

from itertools import combinations

def solution(info, query):
    answer = []
    languages = ['cpp','java','python','-']
    positions = ['backend','frontend','-']
    careers = ['junior','senior','-']
    soulfoods = ['chicken','pizza','-']
    total_dict = {language : {position : {career : {soulfood : [0]*100001 for soulfood in soulfoods} for career in careers}  for position in positions} for language in languages}
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        info_list = [language,position,career,soulfood]
        for i in range(1<<4):
            temp = []
            for j in range(4):
                if i&(1<<j):
                    temp.append(info_list[j])
                else:
                    temp.append('-')
            total_dict[temp[0]][temp[1]][temp[2]][temp[3]][score] += 1
    for language in total_dict.keys():
        for position in total_dict[language].keys():
            for career in total_dict[language][position].keys():
                for soulfood in total_dict[language][position][career].keys():
                    for score in range(1,100001):
                        total_dict[language][position][career][soulfood][score] += total_dict[language][position][career][soulfood][score-1]
    for query_string in query:
        language,position,career,last_query = map(str.strip,query_string.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        answer.append(total_dict[language][position][career][soulfood][100000] - total_dict[language][position][career][soulfood][score-1])
    return answer

 

처음 풀었던 방식이다. dictionary를 이용해서, 각 쿼리에 맞게 저장을 하는 방식이다. 각 쿼리를 저장할때 나올수 있는 겨우의 수는 16가지이다. 그걸 만들기 위해서 조합을 만드는 방식으로 중간에 비트마스크를 활용해서 각조합을 만들고, 저장을 해주었다.

 

그리고 각 score에 대해서 그 이상값을 추출하면 시간이 오래걸리므로, prefix_sum을 통해 저장을 해놓은 뒤, query가 들어왔을때, 최대값이 10만에서 찾고자 하는 값-1을 빼줘서 찾아줬다.

 

해당 코드의 효율성 통과 시간이다.

 

 

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[0]*100001 for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind][score] += 1
    for ind in range(108):
        for score in range(1,100001):
            store_query[ind][score] += store_query[ind][score-1]

    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        answer.append(store_query[ind][100000] - store_query[ind][score-1])
    

    return answer

두번째 코드는 www.youtube.com/watch?v=FX9n1PFv2K4 의 코드에서 차용해와서 푼 방식이다.

 

dicationry로 키를 만드니 너무 난잡해 보여서 2차원 배열로 만든 방식이다.

 

이 방식으로 했을때 시간이 좀 더 빨랐다.

 

import bisect

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[] for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind].append(score)
    for ind in range(108):
        store_query[ind].sort()
    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        cnt = len(store_query[ind]) - bisect.bisect_left(store_query[ind],score)
        answer.append(cnt)
    

    return answer

마지막은 구간합으로 하면  16*100000번의 계산이 필요하므로 실행시간이 오래걸린다. 그래서 해결한 방법중 하나가 bisect라는 라이브러리를 활용한것이다.

 

bisect에 있는 기능 중 bisect_left는 정렬된 리스트에서, 순서대로 정렬되는 것을 유지하고, 현재값이 들어갈수 있는 위치의 왼쪽좌표를 알려준다. 즉, 자기보다 작은 값의 위치를 알려주는 것이다. 이걸 이용해서 그 리스트의 길이에서 해당 index의 위치를 빼주면 이상을 구할 수 있게된다.

 

이걸로 했을때가 시간이 제일 빨랐다. bisect를 이용하지 않고, 이분탐색을 직접구현해도 된다.

 

 

해당 문제는 query로 나올수 있는 경우의 수를 모두 예상하고 저장해놓는게 힘들었다.