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

알고리즘 순위검색

순위 검색

2021 KAKAO BLIND RECRUITMENT

​

문제

프로그래머스

​

풀이

해시맵과 이진탐색을 사용하여 풀이를 진행했습니다.

​

사실 처음에 풀 때 해시맵이 뭔지도 모르고 풀었기 때문에 한참 걸리고 틀리고 힌트를 얻어가며 풀어갔습니다.

문제 해결과정이 꽤 복잡했습니다.

일반배열로 풀고 "시간초과", 집합으로 풀고 시간을 절반 줄였으나 "시간초과", 쿼리 순환 밖에서 정렬해봤는데 "시간초과" 당했습니다.

문제를 보니 info 배열의 크기는 1 이상 50,000 이하입니다. 그렇다면 이중for문은 포기하고 다른 방법을 생각해냈어야했는데 그 방법이 해시맵이었습니다.

해시맵을 사용해서 진행했는데도 "시간초과"가 일어나더군요.

그래서 깨달은 것이 코테점수가 한 key에 다 몰려있는경우 50,000개의 탐색을 진행을 하는거도 "시간초과" 라는 겁니다.

그래서 탐색속도가 빠른 이진탐색을 통해서 해결을 진행했습니다.

​

전체적인 풀이방식을 이렇습니다.

1. 지원서에 입력한 4가지의 정보와 '-'를 포함한 모든 가짓수를 딕셔너리 key로 만듭니다.
2. 해당하는 key에는 배열을 할당해서 해당되는 코테 점수를 넣습니다.
   • 점수 할당시 '-'를 포함한 모든 경우에 점수를 넣습니다.
3. 코테 점수를 모두 정렬합니다.
4. 이제 query를 순환하여 딕셔너리에서 해당하는 key의 배열을 찾습니다.
5. 찾은 배열에서 점수를 비교해서 해당되는 인원을 구합니다.
6. 인원을 구하는 과정에서는 이진탐색을 사용합니다.

​

풀이코드

import itertools
import copy

def binarySearch(li,score,left,right):
    while(left <= right):
        mid = (left+right)//2
        if li[mid]>=score:
            left = mid+1
        else:
            right = mid-1
    return left


def solution(info, query):
    lang = ['cpp', 'java', 'python', '']
    position = ['backend', 'frontend', '']
    career = ['junior', 'senior', '']
    food = ['chicken', 'pizza', '']
    hash_table = {}
    answer_li =[]
    for l in lang:
        for p in position:
            for c in career:
                for f in food:
                    key = l+p+c+f
                    hash_table[key] = list()

    for inf in info:
        tmp_inf = inf.split(' ')
        score = int(tmp_inf[-1])
        tmp_inf = tmp_inf[:-1]
        num = [0,1,2,3]
        hash_table[''.join(tmp_inf)].append(score)       
        for n in range(1,5):    
            orders = list(itertools.combinations(num,n))
            for order in orders:
                ttmp_inf = copy.copy(tmp_inf)
                for orde in order:
                    ttmp_inf[orde] = ''
                hash_table[''.join(ttmp_inf)].append(score)

    for key in hash_table:
        hash_table[key].sort(reverse=True)
    for q in query:
        q = q.replace(" and ","")
        q = q.replace("-","")
        tmp_q = q.split(' ')
        query_score = int(tmp_q[-1])
        answer = 0
        answer_li.append(binarySearch(hash_table[''.join(tmp_q[:-1])],query_score,0,len(hash_table[''.join(tmp_q[:-1])])-1))
    return answer_li
    
    

​

가장 인기 많은 코드

def solution(info, query):
    data = dict()
    for a in ['cpp', 'java', 'python', '-']:
        for b in ['backend', 'frontend', '-']:
            for c in ['junior', 'senior', '-']:
                for d in ['chicken', 'pizza', '-']:
                    data.setdefault((a, b, c, d), list())
    for i in info:
        i = i.split()
        for a in [i[0], '-']:
            for b in [i[1], '-']:
                for c in [i[2], '-']:
                    for d in [i[3], '-']:
                        data[(a, b, c, d)].append(int(i[4]))

    for k in data:
        data[k].sort()

        # print(k, data[k])

    answer = list()
    for q in query:
        q = q.split()

        pool = data[(q[0], q[2], q[4], q[6])]
        find = int(q[7])
        l = 0
        r = len(pool)
        mid = 0
        while l < r:
            mid = (r+l)//2
            if pool[mid] >= find:
                r = mid
            else:
                l = mid+1
            # print(l, r, mid, answer)
        # answer.append((pool, find, mid))
        answer.append(len(pool)-l)

    return answer