[프로그래머스] 순위 검색(python 파이썬)

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

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

사실 처음에 이분탐색 문제인지도 몰랐다.

이분탐색, 사전, 조합 으로 풀었다.

 

처음풀이

key를 점수로 하고 나머지를 value로 넣었다.

사전을 sorted를 이용하여 key로 정렬한다. 

query문의 점수를 확인하여 이분탐색을 통해 사전에 있는 최소로 만족하는 점수의 인덱스를 찾고 그 뒤를 쿼리문에 만족하는 것들의 개수를 찾았다.

정확성 테스트 통과

효율성 테스트 실패 

def solution(info, query):
    answer = []
    # 0:개발언어, 1:직군, 2:경력, 3:소울푸드, 4:점수
    score = dict()

    for information in info:
        temp = information.split(' ')
        if int(temp[4]) in score:
            score[int(temp[4])].append(temp[:4])
        else:
            score[int(temp[4])] = [temp[:4]]
    score = sorted(score.items())

    for commands in query:
        command = ''.join(commands.split('and')).split()
        left = 0
        right = len(score) - 1
        target = int(command[-1])
        while left <= right:
            mid = (left+right) // 2
            if target > score[mid][0]:
                left = mid + 1
            elif target <= score[mid][0]:
                right = mid - 1
        count = 0

        for i in range(left, len(score)):
            for item in score[i][1]:
                if (item[0] == command[0] or command[0] == '-') and (item[1] == command[1] or command[1] == '-') and (item[2] == command[2] or command[2] == '-') and (item[3] == command[3] or command[3] == '-'):
                    count += 1
        answer.append(count)

    return answer

 

 

다음 풀이

사람들의 개발언어, 직군, 경력, 소울푸드의 조합을 가지고 key를 만들고 점수를 value로 사전을 만든다.

query문을 확인하여 문자열로 만든다. ( and, - 제거)

만든 문자열을 사전의 key로 사용하여 해당 value값들을 확인한다.

이분탐색을 통해 최소로 만족하는 점수의 인덱스를 찾는다.

정확성 테스트 통과

효율성 테스트 실패 

from itertools import combinations


def solution(info, query):
    answer = []
    # 0:개발언어, 1:직군, 2:경력, 3:소울푸드, 4:점수
    combi_dict = dict()

    for information in info:
        temp = information.split(' ')
        for i in range(5):
            for combi_info in combinations(temp[:4], i):
                sum_info = ''.join(combi_info)
                if sum_info in combi_dict:
                    combi_dict[sum_info].append(int(temp[-1]))
                else:
                    combi_dict[sum_info] = [int(temp[-1])]

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

    for commands in query:
        combi_command = commands.split(' ')
        target = int(combi_command[-1])
        combi_command = combi_command[:-1]

        for _ in range(3):
            combi_command.remove('and')
        while '-' in combi_command:
            combi_command.remove('-')
        combi_command = ''.join(combi_command)

        if combi_command in combi_dict:
            scores = combi_dict[combi_command]

            left = 0
            right = len(scores) - 1

            while left <= right:
                mid = (left + right) // 2

                if target > scores[mid]:
                    left = mid + 1
                elif target <= scores[mid]:
                    right = mid - 1

            answer.append(len(scores) - left)
        else:
            answer.append(0)

    return answer