[프로그래머스 level2 순위검색] dictionary(hash table) + binary_search 활용하기

해결해야하는 문제는 다음과 같았다.

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

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

 

 

처음에는 직관적으로 해결하였다.

info에 들어온 정보를 table이라는 리스트에 split하여 저장하였다.

그리고 query가 들어왔을 때, -가 있다면 temp_table에 모든 경우의 수를 저장하였기 때문에 접근하여 조건에 맞는 사람이 table에 있을 때마다 count += 1을 해주며 사람 수를 세고, 모든 table을 순회하였을 때 해당 count를 answer에 append해주었다.

모든 query에 대해 이러한 방법을 적용하고자 하였기 때문에 당연히 비효율적일 것 같았다.

이는 정확성테스트는 모두 통과하지만 효율성 테스트에서는 모두 통과하지 못한다.

def solution(info, query):
    answer = []
    table = []
    temp_table = [['cpp','java','python'],['backend','frontend'],
                  ['junior','senior'],['chicken','pizza']]
    for i in info:
        list_i = list(i.split())
        list_i[4]=int(list_i[4])
        table.append(list_i)

    table.sort(key =lambda x : x[4])

    for q in query :
        q_split = q.split('and')
        count = 0
        temp = q_split[3]
        temp = list(temp.split())
        q_split[3] = temp[0]
        score = int(temp[1])
        for i in range(len(q_split)):
            q_split[i] = q_split[i].strip()
            if q_split[i]=='-':
                q_split[i]=temp_table[i]

        for lan,dep,rec,food,sco in table :
            if (sco >= score) and (lan in q_split[0]) and (dep in q_split[1] )and (rec in q_split[2]) and (food in q_split[3]) :
                count += 1

        answer.append(count)
    return answer

 

 

이는 아래의 사이트를 참고하며 만들어졌다...

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

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

 

 

이 문제에 대해 위의 글에서는

hash table 사용하여 접근하기, query에서 점수에 맞는 조건을 탐색할 때에는 이진탐색을 활용하기 라고 되어 있었다.

 

1. table {}이라는 hash table을 생성하였다.

key = 'javabackendjuniorpizza', value = [150] 과 같은 형식으로 저장되는 table을 생성하였다.

info가 들어올 때마다 해당 문자열에 해당할 수 있는 모든 query를 key값으로 저장하였다.

이 때 combinations를 활용하여 기존의 경우 +  '-'가 들어가는 경우 = 1 + 15 = 16가지 경우에 대해 key를 생성한다.

그리고 해당 key를 순회하며 key에 이미 있는 경우는 해당 사람의 성적을 append해주고, 그러지 않은 경우는 리스트를 생성하여 해당 사람의 성적을 넣어주었다.

 

2. 이진 탐색을 활용하기 위해 key에 있는 value들을 sort해준다.

 

3. query문을 key값의 형태와 같이 바꾸어 준 후, 

key가 table에 있다면 이진탐색을 통해 해당 score의 위치를 탐색하여, query에서 제시한 점수 이상의 사람이 몇명인지 알아내어 answer list에 append하였고,

key가 table에 없다면 해당 조건을 만족하는 사람이 없으므로 0명이라고 하였다.

 

4. 생성된 answer list를 return 한다.

 

이러한 방식으로 작성된 코드는 다음과 같다.

from itertools import combinations

def solution(info, query):
    answer = []
    table = {}

    for i in info :
        i_split = i.split()
        table_keys=[]
        for k in range(5):
            for li in combinations([0, 1, 2, 3], k):
                case = ''
                for idx in range(4):
                    if idx not in li :
                        case += i_split[idx]
                    else :
                        case += '-'
                table_keys.append(case)
        for table_key in table_keys:
            if table_key not in table.keys() :
                table[table_key] = [int(i_split[4])]
            else :
                table[table_key].append(int(i_split[4]))

    for key in table.keys():
        table[key].sort()

    for q in query :
        q_split = q.split()
        real_q = q_split[0]+ q_split[2] + q_split[4] + q_split[6]
        score = int(q_split[7])
        if real_q in table.keys():
            start,end = 0,len(table[real_q])
            while start <= end and start != len(table[real_q]):
                mid = (start+end)//2
                if table[real_q][mid] >= score:
                    end = mid -1
                else :
                    start = mid+1
            answer.append(len(table[real_q])-start)
        else :
            answer.append(0)
    return answer

 

 

효율성 테스트는 항상 ,, 접근하기 어려운 것 같다.

효율성 테스트를 통과하기 위해서 해시테이블(딕셔너리)를 잘 활용해야겠다는 점과, 효율적인 것에 있어서 항상 이진 탐색이 등장하는 느낌을 받았기 떄문에 이진 탐색을 활용하기 위해 항상 익숙해져있어야겠다는 것을 알 수 있었다.