손가락놀이터

문제 리뷰

1. 작년에 코딩테스트를 하면서 스스로 많은 부족함을 느꼈고 그동안 공부를 열심히(..?) 해왔습니다! 그러다 프로그래머스에 문제가 나와있어서 지금 다시 풀어보면 풀 수 있을지 궁금해서 다시 풀어보고 리뷰하기로 결심했습니다!😀
2. 해당 문제는 코딩테스트에서 3번 문제로 나왔습니다. 다른 문제와 다르게 정확성과 효율성으로 나눠져있어서 정확성만 맞더라도 부분점수가 나옵니다. 작년에 시험볼 때에도 정확성은 통과했지만 효율성에서는.... 정답률을 보니 효율성 부분은 확실히 낮네용 4.49%.......
3. 단순하게 info와 query를 정리해서 문제를 풀면 정확성에서는 쉽게 해결할 수 있습니다! 하지만 효율성에서 맞기 위해서는 이분탐색을 활용해야 합니다. 대부분의 효율성 문제는 heap정렬과 이분탐색으로 해결가능한 것 같습니다.
4. 이분탐색을 하기 위해서는 info를 통해서 나올 수 있는 모든 조건을 정리해서 전부 입력하는 것입니다. 예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.
5. 모든 조건들을 먼저 정리한 이후 오름차순으로 sorting을 합니다. 여기서 저는 높은 점수가 앞으로 오기 위해서 -1을 곱했습니다. 이유는 bisect_right를 하기 위해서 이고요.
6. info 정리가 끝났다면 이젠 query를 알맞게 가공한 다음 해당 query에서 점수를 이분탐색으로 찾으면 끝이 납니다.
7. 추가적으로 문제를 풀면서 4번 부분에서 처음에는 16가지 그룹을 구할 때, 조합을 활용해서 풀 때는 시간초과가 발생했지만 단순하게 16개를 추출하게 되면 통과됐습니다. 생각해보면 조합이 코드를 구현하거나 보여주기에는 더 깔끔하지만 효율적이지 않다고 생각이 들었습니다.

문제 링크

문제 링크와 카카오에서 제공해준 문제 해설 링크입니다.

from bisect import bisect_right

def get_type(type_arr):
    arr = []
    # 0개 '-'
    arr.append(tuple(type_arr))
    # 1개 '-'
    for i in range(4):
        temp = type_arr[:]
        temp[i] = '-'
        arr.append(tuple(temp))
    # 2개 '-'
    for i in range(4):
        for j in range(i+1, 4):
            temp = type_arr[:]
            temp[i] = '-'
            temp[j] = '-'
            arr.append(tuple(temp))
    # 3개 '-'
    for i in range(4):
        for j in range(i+1,4):
            for k in range(j+1,4):
                temp = type_arr[:]
                temp[i] = '-'
                temp[j] = '-'
                temp[k] = '-'
                arr.append(tuple(temp))
    # 4개 '-'
    arr.append(('-','-','-','-'))
    return arr

# 조합 구현
def comb(lst, n):
    arr = []
    if len(lst) < n:
        return arr

    if n == 1:
        for i in lst:
            arr.append([i])
    else:
        for i in range(len(lst)-n + 1):
            for temp in comb(lst[i+1:], n-1):
                arr.append([lst[i]] + temp)
    return arr

def solution(info, query):

    answer = [] # 결과값
    info_dict = {}  # info에 대한 정리.

    # info값 정리
    for i in info:

        info_arr = i.split()
        # 이분 탐색할 때 큰 값부터 시작하기 위해서 -1을 곱함.
        info_detail, info_score = [k for k in info_arr[:-1]], int(info_arr[-1]) * -1
        # 조합으로 16개를 구하는 방법.
        # info_dict[tuple(info_detail)] = info_dict.get(tuple(info_detail), []) + [info_score]
        # for j in range(1, 5):
        #     for temp in comb(info_detail, j):
        #         info_dict[tuple(temp)] = info_dict.get(tuple(temp), []) + [info_score]

        # 단순히 16개를 구하는 방법
        for i in get_type(info_detail):
            if i in info_dict:
                info_dict[i].append(info_score)
            else:
                info_dict[i] = [info_score]

    # 이분탐색을 하기위해서 sorting
    for key in info_dict.keys():
        info_dict[key].sort()

    # query문 계산
    for i in query:
        # and를 없애고 빈칸 기준으로 나누기
        query_arr = i.replace('and','').split()
        # 가장 마지막값은 제외하고 tuple로 만들고, score는 이분탐색시 빠르게 큰 값부터 시작해서 -1을 곱함.
        query_detail, qeury_score = tuple(k for k in query_arr[:-1]), int(query_arr[-1]) * -1

        # 해당 쿼리문이 없는 경우.
        if query_detail not in info_dict:
            answer.append(0)
        # 해당 쿼리문이 있는 경우 info_dict에서 쿼리문 찾은 이후
        # 이분탐색해서 해당 값이 들어갈 수 있는 가장 끝값 append에 추가하기
        else:
            answer.append(bisect_right(info_dict[query_detail], qeury_score))

    return answer