순위검색[python]

28 Oct 2021

Reading time ~2 minutes

순위 검색- 프로그래머스

기존 코드

def solution(info, query):
    answer = []
    data=[]
    data2=[]
    quest=[]
    quest2=[]
    for i in range(len(info)):
        temp=info[i].split(' ')
        data.append(temp)
        temp=data[i].pop()
        data2.append(temp)

    for i in range(len(query)):
        temp=query[i].replace(' and','')
        temp=temp.replace('- ','')
        temp2=temp.split(' ')
        quest.append(temp2)
        temp=quest[i].pop()
        quest2.append(temp)

    for i in range(len(query)):
        count=0
        for j in range(len(data)):
            if all(check in data[j] for check in quest[i]):
                if int(quest2[i])<=int(data2[j]):
                    count+=1

        answer.append(count)


    return answer

기본적으로 이중 for문으로 인해 O(n^2)이 되었다.
문제는 맞혔지만 효율성은 0점…
효율성이 걸린 문제에서는 이중 for문을 사용할 경우에는 대부분 시간 초과에 걸린다.

kakao tech 문제 풀이

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

문제 3. 순위 검색

본 문제는 정확성 테스트와 효율성 테스트 두 가지 방식으로 검증하는 문제입니다. 효율성 테스트의 경우 주어진 시간 내에 실행이 완료되어야 하므로, 최적화된 구현 방법을 고민할 필요가 있습니다.

우선, 매 문의 조건마다 INFO 배열에서 조건에 해당하는 지원자들을 찾으면서 X점 이상 받은 사람은 몇 명인지 구한다면 정확성 테스트를 통과할 수 있습니다.그러나 효율성 테스트의 경우에는 위와 같은 방식으로 매번 지원자들을 찾는다면 통과할 수 없습니다. 문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 됩니다.

라고 한다….

x점 이상 받은 사람은 몇 명인지. → 해결
지원자들을 그룹별로 적절하게 미리 분류해야 한다 → 미해결

예를 들어“java backend junior pizza 150”일 경우, 앞의 조건이 포함되거나 포함되지 않는 모든 경우의 수가 존재한다.

2번을 해결하기 위해서는 itertools 모듈을 사용하면 된다. → 중복되지 않는 모든 경우의 수 만들어냄

코드 참고

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

사용해야 할 모듈은 총 두 개로, itertools와 bisect이다.

bisect는 파이썬 표준 라이브러리로, 이진 탐색을 사용 가능하게 도와준다.

효율성+정확도 코드

from itertools import combinations
from bisect import bisect_left

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

    for i in range(len(info)):
        temp=info[i].split(' ')
        info_key=temp[:-1]
        info_val=temp[-1]
        for j in range(5):
            for c in combinations(info_key,j):
                temp2=''.join(c)
                if temp2 in di:
                    di[temp2].append(int(info_val))
                else:
                    di[temp2]=[int(info_val)]
    for k in di:
        di[k].sort()


    for q in query:
        temp=q.split(' ')
        query_key=temp[:-1]
        query_val=temp[-1]

        while 'and' in query_key:
            query_key.remove('and')
        while '-' in query_key:
            query_key.remove('-')
        query_key=''.join(query_key)

        if query_key in di:
            score=di[query_key]
            data=bisect_left(score,int(query_val))
            answer.append(len(score)-data)
        else:
            answer.append(0)



    return answer